[SOUND]

Now I want to show you another famous higher order function that recursively

traverses over data structures and then use that to show you more examples using

closures and emphasize what these sort of iterative these higher order functions

are really all about. So it's called fold, it's very similar,

possibly even a synonym to similarly well known names like reduce or inject.

And the idea is to traverse a recursive data structure like a list, in order to

produce a single answer. Okay?

So the wave fold is going to work, we're going to define a function fold, is we're

going to pass in a function f. An initial value, which I'll call ac for

accumulator and a list. And what we're going to do, as you can

kind of see here, is apply f to the accumulator and the first element of the

list. Take that result and pass it to f with

the second element in the list. Take that result and pass it to f with

the third element in the list and so on. So you can imagine, if you imagine your

list laid out from left to right, that you really are folding over it.

You're going over it starting with the accumulator, applying f to the

accumulator in the first element to get another value.

Applying f to that value in the second element, that value in the third element

and so on until you reach the end of the list and that's your final result.

As co, as common a language with higher order functions and convenient syntax

like ML, I can write that function in about three lines.

take in f, then initial commuter and x's, if the list is empty, then the

accumulator is itself the result we want. Otherwise.

Compute f of accumulator in x and pass that, twofold, with f and the rest of the

list. Here, I'm shadowing, this x is here in my

pattern. So this is folding left over the list.

If we write down our list elements, left to right,

we can write a different version of fold that would go from right to left.

that version couldn't be tail recursive quite as well.

And the order doesn't matter, unless it matters for f.

So that's why, in the standard library, they actually do distinguish left from

right. And the type of fold tells you a lot

about what it does. If we type this into the read of l print

loop, what we would get is that the function f can take any two types alpha

and beta. Maybe they are the same, maybe they are

different but it has to return something of type alpha because the older

accumulator and new accumulator have to be values of same type.

That type alpha has to be the type of acc, the accumulator.

The list has the ty, the elements of type beta, that other argument we passed to f.

And then the result of the entire thing has the same type as the type of our

accumulator, and that's alpha. So you start with a beta list, and an

alpha, and an initial answer. You use f to fold over the list,

producing a new answer at each position in the list.

When you get to the end of the list, your final answer is that last alpha.

So that is fold. Let me talk about why we're so excited

about these things. So these iterator like functions are not

built into the language. There's just a programming pattern.

We just wrote it on the slide. It's three lines of ML.

Now many languages provide built in support for iterating over a data

structure and computing a result like, like we would do with fold.

And there's nothing wrong with built in support.

These things are so common. Maybe that's a reasonable thing to do.

they also provide special features like usually you could stop half way down the

list. Whereas fold is all the way, going to

always go all the way down the list. But when we have fold, we can just write

it in our language we have higher order functions and it's really a concept.

We wrote fold here over lists. If we had a different data structure like

an array or a tree or a graph or a set, we could write fold over that as well.

And then, of course, we're going to use fold with lots of different clients

passing in lots of different f. So what I love about this is that it's a

separation of concerns. One group of people can worry about

writing fold over some complicated data structure, lists are not complicated but

there are much more complicated things out there, and then someone else can

worry about how to compute over a particular for a particular result.

And then, if you change and you start using a different data structure other

than a list, you can reuse your function, you just need a new fold.

And conversely once you've written fold for list, lots of different people can

use fold for list for different computations.

So it really separates two things out simply by using a higher order function

and passing one function to another. Okay.

Enough hypothesizing and theorizing. Let's get to the code and show you a

bunch of example uses of fold since you may still be getting the hang of how it

works. I've purposely given all of these

functions non revealing names so you can kind of play along.

So here is fold up here. Right?

Remember it's going to apply f to the accumulator in the first one on the list,

get a result, apply that to with that on the second on the list and so on.

So what we do here in this first call is we pass in some list x's.

Our initial accumulator is zero, and what we do every time, the first argument to

this anonymous function is going to be the next, is the accumulator, the current

accumulator, and the second thing is the next element on the list.

You can see that right here in full. So what we do here at each step is we

take what was the accumulator, and the next element on the list, and we add them

together. That will be our new accumulator.

Then we'll get to the next one on the list, and we'll add that.

Get the next one on the list, and add that.

So when I describe it that way, it seems pretty clear that this is a one line

solution, give and fold, to summing the elements on a list.

Let's do another one. Here I also have a list, my initial

accumulator is true. So at each step, I am going to produce a

boolean. You can't change the type of your

accumulator, so the language with a strong type system and here is my

anonymous function. Remember x is going to be, what the

accumulator, fold is going to pass back into our closure, whatever the next

accumulator is and y is the next element on the list.

So what we do is we take our accumulator and is y greater than or equal to zero.

So if y is, negative, we're going to get false for this whole thing.

If x is false, we're going to get a false for this whole thing, and x keeps

updating with each element of the list. So what this ends up doing is, are all

list elements, positive? Excuse me non negative, if you want to be

picky, alright. Alright?

Okay. So, both those examples do not use

private data. Alright?

These closures we passed in, only use their arguments.

Now, lets see the real power of closures, which is that you can choose other

things. So, here is a call to fold.

x's is my list, 0's my initial accumulator.

x is always the current accumulator. y is the next element of the list and I

am adding to it. So I'm summing something here, but what

I'm adding here is if y is greater than or equal to low and y is less than or

equal to high then one else is zero. Okay?

So notice I am using private data here, low and high, referred to these things

that are only in scope here where I define the function.

But that's great. Closures are powerful that way.

And then I compute either one or zero. So what this is actually doing is

counting the number of elements between low and high inclusive.