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