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