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