[SOUND]

In this segment, I want to talk about the type of the n * function we wrote in the

previous segment. And more generally, talk about the types

of these higher order functions that are taking other functions as arguments.

So, often, the higher order functions we write end up being polymorphic.

They end up having those type variables. A quote a, which I pronounce alpha.

And often, also, a quote b or a quote c, or even a quote d.

Where multiple type variables in the type.

So that can make them seem a little more sophisticated or inscrutable, but it's

actually really helpful. It shows that these functions are so

reusable that they can often take function, arguments, of various types,

the same way we saw n times work over numbers when we were doubling, and we saw

it work over lists when we were taking the [INAUDIBLE].

But the notion of polymorphic types, and the notion of functions taking other

functions as arguments are actually separate issues.

There are high-order functions that are not polymorphic; I'll show you an

example. And there are non-higher-order functions,

first-order functions, we call them, that are polymorphic.

And I'll show you an example you've actually seen before, so I'm really just

reminding you of this. In general I think it's worth focusing on

this because it's always a good idea, when you write down a function, to

understand it's type. What sort of arguments does it work for?

And that's especially true for higher-order functions because the

functions themselves, and their types, are more interesting and complex.

So now let's look at this N times function.

The type it actually has is here on the slide, it's alpha arrow alpha for the

first argument, ent for the second argument, alpha for the third argument,

alpha for the result. So it works for any type alpha provided

that first argument takes and returns alphas, second is an ent, and third is an

alpha. Result is also an alpha.

Now to understand N times it's often helpful to simplify it first.

We could have, given N times a more restrictive type, we wouldn't have been

able to use it as generally but we could have given it a type where all those

alphas are replaced by N's. And this simpler type say if F is a

function that takes and ent and returns an ent.

N is an ent and X is an ent then it returns an ent.

And if you look at the code up here, that makes sense.

Whatever the type of X is, has to be the return type of the entire function.

Because we sometimes return X. So if one of those is INT, the other has

to be INT. And then, the return type of this

recursive call N times, has to be an argument to F.

And the result type of f has to be the result type of m times.

Because the result of this called f is what's returned.

So it turns out that the argument to f has to be the result type of f.

And that has to be the type of x. And that has to be the return type of the

function. But we don't actually care, as the writer

of n times, what that type is. And that's exactly what this polymorphic

type with the alphas in certain positions, is saying.

It's saying, all of these alphas have to be replaced by the same type.

But it works for any type. So, type inference figured this out for

us, but once we have this and we can see it from the [INAUDIBLE] print loop as

we'll see here it's extremely useful to look at this, understand this, and say I

see. F has to be a function with the same

argument and return type. That has to be the type of x and that's

also has to be the same return type. The same function.

So, if we look at how we used end times, we actually did instantiate the type

alpha, or quote a, differently for different uses.

In this call here with double four and seven, we let alpha be INT in every

position. Double, right here is a function from INT

to INT, four is an INT, that has to be an INT here, seven is and INT, that's this

third argument. And indeed the result type is INT.

For increment it was the same. We also instantiated alpha with int.

But for nth tail, we actually instantiated with int list.

We can see that most easily with this argument here, the third argument.

That alpha before the arrow, is clearly an int list.

Entail as it self polymorphic it coumored for any type of list and returns a the

same type of list so it is correct as a function from it list to int list which

is the correct type for the first argument here.

And the overall result ends up being an int list.

So that's just polymorphic functions, it's not really anything new.

It just sometimes looks a little bit more mysterious once you start seeing these

function arguments. but it makes our code a lot more

reusable. If we didn't have polymorphism here, we

would have to write one version of n * for integer arguments.

And another version of n * for int list arguments.

And that would make the whole idea of reusable code and first class functions a

lot less persuasive. Okay,

so that is end times. That is the reason why we saw the type we

saw from the read eval print loop. Now let me try and convince you that

there are. Higher order functions that are not

polymorphic and polymorphic functions that are not higher order.

So I've an example of each here. the first is this function called times

until zero. Let me tell you what it does.

It takes in a function F in an argument X and it counts how many times you need to

do [SOUND] F, of F, of F, of F, of X until you get zero,

okay? So what's the first time, the first

number of S, at which the result is zero? So I've implemented that right here.

If x is already zero, then we need zero f's.

Otherwise, we need one+ the number of times to get to zero from f of x.

So we're going to now start with f of x for our recursive call, using the same

function F. And since that's one extra step of F,

that adds one to the result. Okay, and so that is a nice function and

it turns out that its type is, let's see F has to be an ent error ent and X has to

be an ent and then the result is an ent and why is that?

Well X has to be an ent because we compare it to zero, okay?

F has the taken end. Because right here, we call it with X.

X has to be an end, we call F with X. F has the taken end.

And therefore x has to return an int, because it's past as the second argument

to times until zero. So it turns out that this higher order

function that is convenient and reusable. You can imagine using it in many

situations for seeing if some function converges or something only works with

integers. It just doesn't make sense otherwise, you

can't say how many times do you have to convert a string into a different string

until you get zero. That doesn't make sense.

Strings will never be zero. You cannot compare them with zero.

So, not a polymorphic function but nonetheless, a useful high order

function. Conversely, here's a function we've seen

many times. It computes the length of a list.

and its type is, it will take a list of any type and return an integer.

Doesn't care what the type of the elements are.

It never looks at them. In fact, we could replace this pattern

here with a wild card that would arguably be better style.

So, it has a polymorphic type. But there's nothing, there's no first

class function in sight. It just takes a list and returns an

integer, okay?

so that is our contrast. Hopefully, now we understand the type of

end times better, and we understand the relation between polymorphic types and

functions as arguments.