0:00

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

8:01

Me. It's almost one line long.

It got a little long for me. Okay, here's another one.

this is similar to something we did in the previous segment, now I'm going to

take in list of strings and a string. And I'm going to call fold, I'm going to

produce a boolean here, starting with the list exis, and my closure here says x and

also something, so I'm doing the same game as I was doing previously of

computing is something true of every element of the list.

If you fold over in this way you're going to do a for all if you will,

are all elements of the list such that there size is strictly less than i, where

i is this variable I can bound up here computing ones to avoid recombination,

the size of the string s. So, what this ends up doing is computing

our all elements of the list, strings whose size are strictly less than the

size of s. Okay.

And I avoided recomputation like we saw in the previous segment.

one more example here of some different function, this one is more generic.

Okay. So f5 takes in a function g and the list

x's. And it passes x as the fold, initial

acumulator of true, but what it does is it says x and also g of y, so now call is

of f5 will pass in a function that says well this is how you decide if this

element to the list passes the test. And it's f5's job to use full to see if

therefore do they all pass the test? So this is really saying do all elements

of the list produce true when passed to g?

And now, given that reusable function, I could redefine f4 without using fold

directly. I could just use f5 as my helper

function. And all I have to do is call f5 with this

simple anonymous function, and the list x's.

So this is just another way to use higher order functions.

f5 is using closures here. Notice this g is defined where the

function is defined. Alright.

So that was several examples, and let me just remind you why I'm showing you this,

which is that map filter and fold do become much more powerful, thanks to

closures and lexical scope. We can pass in any private data that are

function f means, just by using scope. and the iterator folded itself doesn't

need to what data is there or even what type it has.

So our first couple of examples, f1 and f2 I believe didn't use private data and

that's fine. f3, f4, and f5 did and that's fine too.

Fold works the same way. It just calls f once for each element in

the list and f can use whatever is in it's environment.

So, now we've seen map, filter and fold. Probably the three most important higher

order functions there are. Of course, there are many other useful

ones. In fact, the f5 we just defined is itself

a very useful higher order function. It's easier to use, simpler to use than

fold. But we nonetheless defined it using fold.

And that's the end of our study of fold. Now we can continue to study other

idioms, other important ways that we can use closures.