[MUSIC] In this segment we're going to start our study of currying, our next
closure idiom. It's one of my favorite things to do in
functional programming. and this is a new way to deal with
conceptually multi-argument function. So you might remember that in ML, every
function takes exactly one argument. We worked around this previously by
passing n arguments as n different pieces of a single tuple.
So another way we could do it which is called currying, is to take one argument
and return a function that takes the next argument and it we'll still be able to
use the first argument, because it will be in its environment.
This is called Currying after the name of the person just as a funniest side, I
actually spent years of my life before I knew that, trying to figure out why it
was called currying, and of course, I was never successful.
So, let me show you an example in the code of how this is going to work.
So, we are going to stick with a very simple example in this section of just a
function that takes three arguments conceptually, x, y and z and sees that
they're sorted. So in terms of tupling, just take a
triple, pattern match against it like this, and return true or false based on
is z >= y and is y >= equal to x. And we would call that tupled function
with a triple like 7, 9, 11. So here is a new way to do it that at
first will seem very ugly, but then I will show you some syntactic sugar that
will perhaps make it even cleaner, even more pleasant than the tupled version.
So let's just make a sorted3 function that takes in an x and returns, these
parentheses are not optional or are optional, so I'm going to take them out,
a function y that when you call it, returns a function z, a function that
takes a z, and when you call it says z >= y and also y >= x.
Now that looks a little funny too, we could have instead said it fun sorted3
taking an x and then return a function y that when you call it, takes a function z
and so on. That's exactly the same thing so maybe
the val version will be a little easier here.
And now, what we can do is we could call sorted3 with a number, like 7 and that
would give us back a function, right? If we call this with x, we're going to get
back this. So what we could then do is call that
function with 9 and that would give us back this function,
and then we could call that with 11. And this will absolutely work and should
even give us the right answer, so let's see.
sure enough I have some lower stuff in the file, ignore that.
sorted3_tupled takes a tuple of ints and returns a bool.
t1 was true. Sorted3 takes an int,
returns a function that takes an int, and returns a function that takes an int, and
that all returns a bool, and then we did use it correctly, and so
t2 is true. So let's take a closer look at what's
going on, because that looks awfully complicated.
It's all the same semantics, we already know about closures.
So when we called (sorted3 7), we got back a closure.
Remember, a closure has two parts, a code and an environment.
The code is just the body of the function we called fn y, fn z, z >= y, and also,
that's the function we got back, we called with (sorted3 7).
It returned this function that takes y and the environment for that closure is
that x maps to 7. So when we call that closure with 9, we get back a closure
whose code is now fn z, z >= y and also y >= x, because that's what the result is
of calling the function with y to 9 and in the environment, x maps to 7 and y
maps to 9. So when we call that closure with 11, we
evaluate the and expression, and we get back true,
that's all there is to it. And, while the semantics may seem
complicated, it's just closures which we get used to.
And since currying is such a common pattern, such a common idiom,
we don't think through it on this level every time.
We just say oh, I'm using currying, so it's like a multi-argument function.
And, so now, let's make it even more pleasant to use by pointing out some
syntactic sugar that we happen to have in ML.
So, it turns out, the first thing we can clean up is this call.
Okay? So we don't need all these parentheses.
In general, if you just leave the parentheses out with spaces between
arguments, the parentheses go in to organize things
to the left. So if you just write sorted3 7 9 11, it's
calling sorted3 with 7, getting back a function and calling it with 9, and
getting back a function and calling it with 11.
So we don't need those parentheses. We can go back to our code here and instead,
just say val t3 = sorted3 7 9 11. And now if you compare this to calling a
tupled function, it's actually fewer characters, more space characters, but
less clutter on the screen, so that's actually kind of nice.
And this is a good time to point out that you have a curried function, like
sorted3, you can call it either of these two ways.
If you have a tupled function, you can only call it this way,
you can't mix and match, right? If you want to call a function
that takes a tuple, you have to pass a tuple.
And if you want to call a function that takes, that's curried, you have do via
via a sequence of calls. So you can't, for example, write
sorted3_tupled 7 9 11. That's going to try to call
sorted3_tupled with 7, you'll get a type error immediately,
because you're not passing a tuple where you need it. And similarly, you cannot
call sorted3 with a tuple, you will also get a type error. It doesn't expect a
tuple, we can see here in the greater than, y >= x, that x needs to be an int
and not a triple int, so we better comment all that out.
Okay? So, so far, so good. That's the first step of syntactic sugar,
is that callers can just think oh, it's curried and takes three arguments.
I'll just separate them by spaces. It's also easier to define curried
functions than I've suggested, that you don't have to write all these
anonymous functions that return other anonymous functions.
That you can, or syntax for function binding has built in support for
currying. So, I have the definitions here written
on the slide, but it is sometimes easier just to show an example.
Here is another definition of sorted3, which I'll call sorted3_nicer.
If you just separate multiple patterns in general, here just variables, before the
equals, this means curried Alright? So y >= x, and so, compared to our
previous version here, these are exactly the same,
this is syntactic sugar for this, although, because we used fn, we could
also use recursion, we don't need recursion here.
So given this that's a much nicer way to write the function, and we can continue
to use it using our syntactic sugar, and that is a really nice way to think of
multi-argument functions. Just the caller, separated them by
spaces, the callee and the caller, separated them by spaces, but what is
going on semantically is closures, functions returning other functions,
the rest is just syntactic sugar. I would point out that because this is
just syntax, you could call sorted3_nicer with all these parentheses, because this
means exactly the same thing as the line and a buff, 'kay? So that is what most of
what I wanted to show you. Remember here, over in the over in SML,
in ripple, that these tupled functions will print their arguments looking like
this, sorted3_nicer, we'd have exactly the same
type. Remember, the parentheses go to the right
here, so this says, I'm a function that takes
an int and returns an int -> int -> bool. meaning that you passed that function in
int and you get back a function, you pass that function in int and you'll get back
a bool. So as you can, here in the alpha to the
ripple, I had one more thing I wanted to show you,
which was a fold in a curried form. So we've seen fold before, it was a
couple of segments ago. Here is a version that takes three
curried arguments using our syntactic sugar. So this first line right here that
I'm highlighting, means exactly the same thing as on a function fold that takes f
and returns a function that takes the accumulator.
If you call that, it returns a functions that takes x's and this is its body. And
you'll notice that here in the recursive call, since I have a curried function, I
need to pass those arguments separated by spaces and I've done that.
Here is the first argument, here is the second argument, and you need
these parentheses so that you know where the second argument ends and this third
argument begins. So that's a perfectly fine curried
function. Here is a use of it.
Here is a function that sums all the elements in a list by just calling fold,
which here is curried. Here's the first argument, space, second
argument, space, third argument, exact same semantics as sorted3,
just more useful. So, coming back here, in terms of
sorted3, our final version here is really very elegant.
It's actually fewer non-space characters than the tupled approach, the approach
that used tuples, and we just know that it's syntactic
sugar for this bottom version, which is easier to understand what's going on.
But once you get it, once you go oh, that's what curring is doing,
then you just think of it as a three argument function, like we've thought of
tuples as multi-argument functions. And then for fold, we just write it this
way to begin with. It's just as elegant.
We think of fold as a three argument function and we call it with three
arguments.
Dan GrossmanProfessor
