[SOUND] We've now seen a number of examples of first class functions,

including my favorites, map and filter. But all of our examples so far have been

similar enough that I want to emphasize now just how general first class

functions are. So, so far our examples, N times, map,

filter and probably a couple others, have all just had one function that took one

other function as an argument and then recursively processed numbers and lists.

So I just want to remind you that we can use functions wherever we can use any

kind of expression. This is actually a useful thing to do.

So a couple things I won't show you examples of in this segment are passing

multiple functions as arguments to a function.

The same way we passing one function that I've been calling F.

To abstract over some sort of computation.

If you had two different computations you wanted to abstract over. It would make

perfect sense to pass in, have callers pass two different functions.

So that's the first thing we can do with the first class functions we haven't seen

so far. Another one is we can put functions in

data structures in tuples or lists or records.

And I'll show you an idiom that uses that later in this section of the course,

but we're not going to do it quite now, because we want to have some other

features and study some other things first.

But two things I am going to do in this segment are have functions return other

functions as results, just a silly example to show you how that

works. And then, we're going to write a high

order function over a data structure that is not a list, that's actually one of our

own data type findings. All right.

So let's do the returning functions first, and how about I just show you the

code to start with. So here is a function that actually takes

a function and also returns a function. So it takes in an argument, F, and it

calls F with seven, that's how I know it's an argument.

So in fact, for this part to type check, I can tell you that this function overall

has to take in an int arrow bool, that, that needs to be the type of F.

All right. But then, if you look at the then branch

and the else branch, in each case, it returns a function.

It turns out an anonymous function. Although you could have any expression

there that evaluated to a function, and in both cases, since we know then and

else always have to have the same type, we have functions of the same type, and

in fact, this function always returns an int arrow int.

So the function binding for double or triple defines a function that takes in

an int arrow bool and returns an int arrow int.

Oops, sorry about that. So let me show a couple of uses of this.

here's, I'm going to write down an expression that's going to end up

returning the first function that given X returns two times X.

So I'll bind this to the variable double. If I, all I have to do is call double or

triple with some argument that will cause F of seven to evaluate to true.

So there's any number of them but how about X minus three equals four.

Okay? If I called out I'm going to end up

getting the double function back. Notice that double is not a number.

It's a function, because double or triple returns a function.

We could take that and then call it, or we could take another call to double or

triple, maybe something that returns false, like fun X, X equals 42,

that will not return true when applied to 7.

If we could just take that entire expression which will end up being the

function that takes its argument an multiplies it by three and if I call that

with 3, I'll end up with 3 times 3, which is 9.

Okay? So how about we try all that out real

quick? Use generalizing dot SML.

And sure enough, double or triple is just about the type I told you.

We'll get back to that in just a second. Double is indeed an int arrow int,

and to make sure it's the function we think it is, yes indeed, double zero four

returned eight, and this last expression I wrote down did indeed evaluate to nine.

Alright, so now the only remaining thing I want to talk about here is how I said

the type of double or triple was this, taken int arrow bool, returning int arrow

int. And the REPL said this type, and just

left off the parentheses around the result type.

It always does that, the REPL never prints parentheses it does not have to

and it turns out that those parentheses are optional.

So to see that let me show you the general rule which I have down here at

the bottom of this slide. When you see a type like T, with multiple

arrows like this, like T1 arrow, T2 arrow, T3 arrow, T4, the implicit

parenthesis are always on the right. So this for example would be a function

that takes a T1 and returns another function that takes a T2, that itself

returns another function that takes a T3 and then returns a T4.

So when you're first seeing functions that return functions, you really wish

the REPL would put in those parentheses for you.

It's not going to, so you have to put them in yourself in your head.

And you get used to this fairly quickly and then you end up liking, in fact, the

conciseness of leaving off the unnecessary parentheses.

Alright, so that was functions returning other functions.

Now let me remind you that high-order functions are not just good for numbers

and lists. They're a great way to process, for any

sort of recursive data structure, where you might want to do the same sort of

recursive traversal with many different possible, computations.

So for an example of that, let me go back over here and scroll down.

I have our old friend, this data type binding for arithmetic expressions, and

suppose I give you a homework problem like, given an X, one of these things, is

every constant in it an even number? You could write that recursive function,

but suppose I had another homework question that said is every constant in

it less than ten. And you could write that as well but it

would be very, very similar and if you had a bunch of these traversals that were

all of the form is something true of every constant.

It would be a great idea to abstract that kind of traversal, that kind of

processing of the data, into a higher order function.

So let me, show you how may, might, we might do that.

I might write a function true of all constants.

It's going to take in a function and an E, and it's going to say, does F return

true. For every constant.

So it's a lot like a filter, in the sense that we're going to call F on every

constant in here. But it's not a filter, it's going to, the

whole thing is going to return true or false.

So if our entire expression is a constant, then I just want to call F.

On that constant and all the other cases are just recursively calling true of all

constants on the sub-expressions, so that we can find all the constants.

And this is the sort of thing that's fine to write out once but it'd be a pain to

write it out over and over again for all the different questions we might have

about the constants and expressions. So it's great that we're abstracting it

into a higher order function that then we'll be able to use multiple times.

Okay? And I think that's right.

And then it's such a pain to write this out. I'm even going to copy and paste

just a little bit and write multiply there.

And now, if I wrote this once, and I wanted to write the function that I

started with, all even. Take an expression, are all the constants

in it even? Then I would just say, true of all

constants, and pass in a little function that asks if the argument is even, and

call that with E. And let's see if I got all that right.