[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. [SOUND]. And I at least got the types right. all even is indeed a function that takes in an X and returns a bool. Yes or no, are all the, the constants even? True of all constants is one of those high order functions that has nice type that it really kind of explains a little bit what's going on. Although not completely, you still need documentation for the function. It takes in an X and an int arrow bool, because we know that we take that function argument. We apply it to constants, and then the entire thing, the result type is bool. Yes or no, the and also is combined to return true or false based on whether all the constants, are true according to this int arrow bool argument. So when you have these functions that have return type bool like this, that process some data, I like to call them predicates. It's a nice mathematical world. The predicate is something that returns true or false for something, and this is an example of a higher order predicate. It takes in, it abstracts over that computation, says give me any integer bool and I'll give you a predicate that uses that int arrow bool.
