[MUSIC] In this segment, let's get right to studying probably the most common use of first class functions which is passing one function as an argument to another function. So, I want to emphasize that there's nothing really new here in terms of language features, we just never thought to do this before. So, we could define a function binding in ML, say, f that took as one of its arguments another function g. And then inside the, the body of f, g would be a variable. That when we look it up, we get a function. And so, we could call that function with some arguments. And so, we could use f in one place calling it with h1. And in another place, calling it with h2. So, that makes f more useful, more parameterizable because different callers of f can pass in different functions. This is going to be a very elegant strategy for us. We're going to be able to take common pieces of code and abstract them out which is one of the best things to do when you're designing software. And the way we can abstract them out is instead of having n very similar functions, we could have one function that has all the common parts and then, pass in n different shorter functions that just describe in their bodies and their computations the parts that are different. So really, the rest of this segment is going to be over in Emacs showing you a good example of this, a simple example of this to give you a sense of how this might work. So, to start with, I already have written here three ordinary non higher-order functions. Plain old first-order functions, we call them. but they all have quite a bit of similarity, which we'll see. So, they're a little silly, but bear with me. This first one just takes two arguments n and x and increments x, n times. So, if n is zero, it just returns x. Otherwise, it returns one, plus the result of incrementing x, n minus one times. Now, this really is quite silly. This is an addition function. It's just taking x and adding n to it, but, but that's okay. The second example is a bit less silly. There's no built-in operator for it in ML. It takes a number n and another number x and it doubles x, n times. Put it another way, if you're a little more familiar with your math, it's two to the n times x, alright? And the way it does it is it says if n is zero, return x. Otherwise, multiply by two the result of doubling x, n minus one times. The last example doesn't necessarily work with numbers at all, it works with lists. Takes a number n and a list x's and it takes the nth tail. So, for example, if you pass it three and the list 4, 8, 12, 16, then you would get back the list 16. Because if you take tail of tail of tail of that input list, you end up with the list holding just 16, okay? How does it do it? If n is zero, then just return the entire list. Otherwise, take tail of the nth tail of n - 1 and x's. Alright. So, three simple functions we could have already written ourselves. But hopefully, it pains you to see so much similarity between these functions. All of them take two arguments. If the first argument is zero, return the second one. Otherwise, do something to the recursive call with x or x's and n minus one. So, somehow we'd like to separate all this out so we don't have to write all that stuff three times. And in general, these might be bigger and more complicated. and the only way we can do this without first class functions which would be some ugly kluge, where we had some flag. Do I want to be increment or double or nth tail? And that's not extensible. What if there's a fourth function that comes along that is like this? But first-class functions do this very, very well. So, what I'm going to do is write a function n times. That, in addition to taking n and x, takes another argument, f. And that f is going to capture the differences between the three functions above. So, in every case, I want to say, if n0, = 0, then just return that second argument. Otherwise, I definitely want to call n times with the same function n - 1 and x. And then, what I want to do to that recursive result, well, that depends. And it depends on whether I want to do doubling or incrementing or tailing. but in all cases, we'll just have the caller pass in an f that does what we want. So, that is our useful higher-order function and now let's see how we can use that to do incrementing and doubling and tailing. And so, let me first just define a couple very simple and very short helper functions like this. There are various ways you can double there's one, right? And now, what I can do is use n times in various ways. So, if I wanted to double seven four times, then I would just do that. And if I, oops, sorry. x1 equals, there we go. if I wanted to increment seven four times, then how about I make the exact same call, but I pass an increment instead. And similarly, if I wanted to take the tail, so maybe two tails of a list like 4, 8, 12, 16, it'll work just like that. And sure enough, if I come over here and run it, functions as arguments.sml. You'll see that x1 is 112, x2 is eleven, and x3 is 12,16. So, we saved a lot of code reuse here. We got a lot more code reuse. All we did here was use n times, increment double, which are very short and then, use it in different ways. Now, you might be thinking, well, that's great. But, you know, callers, you know, users of my code shouldn't have to go to this extra work. But, of course, they, they don't have to, right? If I want to write my own increment function that takes n and x. And how about I change its name, since we know this is really just addition. As long as n is greater than or equal to zero, none of these functions work for negative n. I can just define this like this, right? The function that takes n and x and increments x n times can be implemented by calling n times with increment n and x. And similarly, double n times could be better written as this body. [SOUND] And finally, nth tail, n, x can be written as this. And as always, callers of these functions don't need to know and don't need to care that we've implemented them using the same common code, n times, under the hood. And then finally, suppose we did this, we are very happy with ourselves, we can now go up and really get rid of or for the sake of simplicity, I'll just comment out all this repetitive code. So, all we have now is n times and these three helper functions, and then maybe sometime later, you'll realize that that pattern, that reusable code, that higher-order function n times is even more useful. Maybe you come along and you realize that oh, you need to triple some number n times, n, x. And you're like oh, well, I'll just call n times with a little helper function triple that I'll write and n, x. and, of course, I need to define triple here. And it'll be three times x, alright? And this is all wonderful. and let's go back and make sure we got that all right. And sure enough, what we now have are functions additional, addition and double n times, both of int star int arrow int. We have nth tail of type int star alpha list arrow alpha list and triple n times of int star arrow int. So, n times which fundamentally just takes a function and an n and an x and ends up returning f of f of f of f. N times of those applied to x is a generally reusable, beautiful high-order function that we can reuse by passing in different functions in that position for f. So, that seems like a great example. The only thing that might be a little confusing to you is this type of n times which looks a little complicated in polymorphic. And so, let's talk about that a little bit more in the next segment.
