[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,