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