All right

so I'm substituting for Professor Kohlhase today one more time.

He is not around.

I'm one of his PhD students.

And today we will talk more about standard ML or SML.

That's this programming language that is introduced in the lecture.

And you started last week already

and we will continue going over different aspects

of it.

And we start with higher order functions.

Higher order functions basically is a fancy word for saying functions are also just values.

You can give them to other functions as arguments

and functions can return functions as return

values.

So there's an example that's using the map function here.

Okay, you can't see anything like that.

Let me use the cursor.

So what we do here is we define a function first, f.

It's a very simple function.

It just increments, like returns the number plus one.

And we use the map function.

That's one of the functions in the library

which takes a function as an argument and

applies it to each element of a list and returns a new list with all the values that you get.

You get that way.

So in this case

we apply the function that increments by one to this list

and as a return

value, we get two, three, four, five, right?

Each element plus one.

That's a very simple example.

We pass a function.

And this map function is a higher order function.

So that's the example for that.

And now we can start to wonder how could we implement something like that ourselves if

the standard library didn't provide map?

How would we go about it?

And so here we have an implementation.

We call it myMap.

And we have to do two cases.

So we do the whole thing inductively in a way.

We have the base case, so the empty list.

And if we map a function over an empty list

nil

then we return the empty list.

And then the other case

if we have a non-empty list

then I hope you remember this colon

colon notation means h is the first element of the list and t is the rest of the list.

So in this case, what do we do?