[SOUND] In this segment we're going to write and use two more high-order functions, which we will call map and filter. And these examples are so famous, so important, I like to joke that if there were a hall of fame for famous higher order functions, these would be in it. These are not functions I made up, I didn't make up their name. In fact, they're part of the common vocabulary that computer scientists and software developers use all the time. So it's important to understand when map and filter are the right thing to use and it's great that in a language with higher order functions, we can easily define them for ourselves over data structures like lists. So let's just do that. I've just got a blank file here, and we'll do map first. So we're going to do map over a list. Map takes a function and a list, and what it does, is it computes a new list that is like the input list, except F is applied to each element. So it's got the same shape and size. The Ith element of the output is the Ith element of the input with F applied to it. And once you know how to write higher order functions in a language like ML, this is actually very easy. let's just case on X's. If we have the empty list, then the result of mapping F across all of those elements is simply the empty list. Otherwise, we'll have a non-empty list, and what we should do is create a list that's F applied to X consed on to mapping F to X's prime. That is the entire thing that, for map, and if it looks a little familiar, it might be because it's on the course logo you've seen every time, you've participated in this course. All right. Let's see how to use map in a couple different ways. one thing we could do, I'm just going to define a couple variables here, is we could map the increment function, take X return X plus one, across a list of integers. Maybe four, eight, twelve, sixteen? Or we could, let's say map the head function. Notice I'm not unnecessarily wrapping it here, across a list of lists. You're going to have to have a list of lists, because we're going to apply head, which requires a list to every element of a list. So we do need a list of lists here. I'll make my list of lists, list of lists of integers, and there we are. Alright, and now let's save this and try this out. Use map and filter.sml, and sure enough x1 is the list 5, 9, 13, 17, and x2 is the list 1, 3, 5, which is what you get if you take the head of these three lists here. their type of map is quite interesting, and let's talk about that just a little bit more back here with the slide. So here you see the code we wrote for map, and the type that we saw from the Read About print loop is that map takes two arguments and returns something. That's definitely true. The first argument can be a function from any type alpha to any type beta, quote A arrow quote B. The two types don't even have to be the same. But there are some constraints, the second argument to map has to be a list of alphas. So whatever the element type is of the second argument has to be the argument type of that function F. And what map returns is a beta list, a list whose elements are whatever type this higher order function takes as its argument. So it's very elegant to understand map. You need to understand its type. It's an alpha aero beta star alpha list to beta list. Alpha and beta can be the same. In this first example, where we incremented every element of the list, we instantiated both alpha and beta with int. But in this second example, where we still have map of the same type, alpha is int list. Head takes an int list and beta is int, because that's what head returns when given an int list right. So that is map. once you've learned it, once you've seen it, you end up using it all the time. It's very often good style to use map because it communicates to the reader of your code, what I'm doing here is a map operation. I'm applying the same function to every element of some collection to produce a corresponding collection. All right. In fact, it's so common, it is pre-defined in standard ML standard library, although it has a slightly different style. It's, it doesn't have quite the type I've shown here, because it uses this thing currying, that we're going to get to in a few segments. But it's a, it's a very similar function that also performs mapping. All right, so that was map. I promised you two hall of fame higher order functions, so let's do the second one. This is filter. It also takes an F and a list of X's but F works differently here. Here we expect f to return true or false, and what we're going to compute is a list that's a subset of the elements in X's in the same order. And what we're going to do is we're going to filter out any elements of X's for which F returns false. So once again, we need a case for the empty list and a case for the non-empty list, and if you don't start with any elements, no matter what you, there will be nothing to even potentially filter out. You'll just end up with no elements, whereas if you have a non-empty list, well, whether to include X in the output or not depends on what F of X returns. If F of X returns true, then we want X in our output, and the rest of our output should be the result of filtering F with X's prime. Otherwise, we just want to have F of X as prime. There are other ways we could have written this. for example, we could have written if. if fx, then and try to append the result. But this is probably the most elegant way, and it says pretty directly what it is we're trying to do. as before we can write a couple simpler examples of this. Instead of actually showing examples that process actual lists, how about we define some functions that use filter as a helper function. so for my first example, I'll write this out with a top-level function so it's a little easier for you to read. If we wanted to take a list of integers and return only the even numbers out of that list then I could write a function all even. That just called filter with that is even function I just wrote and x's. Alright. Here's a more complicated example that's going to use a more sophisticated anonymous function, just because I thought it would be fun. Let's take a list of pairs, where the second thing has to be an integer, and return the elements where that second thing is an even integer. So, I'm using a little pattern there in my anonymous function. I need to write the fun keyword here. Okay. and X's. and I have too few parentheses. How about right there? I think that's right. let's go over and try this. And sure enough, all even is a nice filter function from int list to int list. Let's try it out really quick. All even of 3, 4, 6, 0, 13. And we get back the list 4, 6, 0. I'll leave it to you to test out all even of the second things of pairs, if you're interested in that one. Okay? So, filter, which you see here on the slide, is also one of these very famous functions. It's just part of the vocabulary of computer science. Also in the standard library using that currying feature we'll get to. But let's finish up this segment by looking at the type of filter. It does take a list of alphas and it returns a list of alphas. Unlike map we're not computing anything based in terms of the elements. What we're returning is a subset of the elements, keeping the same order and so the alpha list for the argument can be the alpha list for the result. We can pass an ent list, string list, lists of lists of ints, whatever but the output list will have the same type. And the argument for F, that F argument, has type alpha aero bool. We definitely pass elements of the argument list to F, so it has to be the same type that F expects and that the elements of the list have. And F needs to return a bool because we use it right here in the position between if and then, and we know from very early in the course that for an if then else to type check, the result of this expression after the if has to have type bool. So there you are, probably two of the most famous functions in all of computer science, map and filter.
