[MUSIC] I want to show you one more idiom that helps us avoid repeated computations and how it's useful. Turns out this idiom does not really use Thunks. But that's okay its still worth knowing, its called memoization. Which is not an English word, but it is a technical word we use for this and we really do leave the r out and call it memoization, not memorization. And its been called that for a long time. So here's the idea. If a function has no side effect and doesn't read anything that can change. There's no point in computing it twice for the same arguments. If you call it twice with seven, you're going to get the same answer. If you call it twice with the same list, you're going to get the same answer. It doesn't matter how many times you call it. So what you could do is keep what's called a cache of previous results. Keep some data structure that remembers, hey if you call this function with seven, this is what you're going to get back. And this can be a great idea if maintaining and using the cache is cheaper than recomputing the results. And if people actually do the recomputations, they actually call the same function with the same argument again. Otherwise, the cache is a waste of space and a waste of time. This idea is really pretty similar to promises, that thing we saw with force and delay, right? That when we do the first force will store the result, so when you later force just has the result there. But force and delay was for thunks that don't take any arguments. Once you take arguments, you can't just have one thing that you store for future reference. You need a table of them, depending on what the arguments are. So that's where memoization is a little more sophisticated. Now I'm going to show you an example where using memoization with a recursive function actually leads to a program that is exponentially faster. And so it's a common technique, something you can apply almost mechanically that can actually lead to programs that are much more efficient. Other times they're just a little more efficient and it's still considered a convenient thing to do. So I'm going to show the most of the rest of this with the code. I'm going to use this classic example for memoization, this is what most people use. Here's an implementation of the Fibonacci function. This is a function for mathematics the same way we've been using factorial. Which says that factorial of n is n times factorial of n- 1 with a base case of factorial of zero is one. Fibonacci is a little more sophisticated. It says Fibonacci is one for both one and two. So just read the racket code here. If x is one or x is two, it's one. Otherwise, it's the sum of Fibonacci of x minus one. And Fibonacci of x minus two. So you see two recursive calls here and turns out that these two recursive calls cause this to be a very inefficient implementation. This is exactly how it's defined mathematically. You call Fibonacci one with 30 you get a nice big number like 830,000. But if you call with 40, this takes about 1,000 times longer to evaluate. And I don't have 1,000 times longer to wait, so I'm just going to stop this and say this is not a good implementation of the Fibonacci function. Okay, so what are we going to do about it? Well one thing you can do which I'm not going to focus on here is throw away that algorithm and implement this other bottom up algorithm. That uses a local helper function that takes an accumulator and starts at low numbers and figures out Fibonacci up to high numbers by adding the two previous numbers as you go along. You're welcome to look at the code. It's not that complicated. I just want to admit that this algorithm exist before moving on and showing you a different way to do this efficiently that shows this idea of memorization. So we're going to forget about that second version. Just move on to the third version. I know it looks big and complicated. We're just going to go through it line by line and see there's just implementing this idea of keeping around all the previous results. So anytime, we compute Fibonacci of anything we're going to put it in our table. And because we're going to do that even when we make recursive calls, it's going to turn Fibonacci into an efficient functions. So let's see how that works, so the first thing you'll notice is that Fibonacci ends up just being this helper function f. So I'm going to define this function f here and then just return it. And the reason why I'm doing that is I need f to use this memo table, this cache, this thing that is initially null, but is bound to this variable memo. It's essential, I don't want memo to be up at top level. I don't want to define memo up here because this is an implementation detail. I don't want to expose it to the outside world. But I also cannot put it inside this function I am going to define. Because if you put it inside we're going to recreate a new table every time we call this function. Because we do not execute function bodies until we call them. We need it outside the table so that it persists. So it's still around from one call to the nest. And it's initially null. And we're going to use mutation to update it appropriately. Okay, so when we want to find Fibonacci of x, so we just call x right here. The first thing we're going to do is see is it already in the memo table? So here I'm using a little library function assoc, that takes in something and a list, and tells you if that something is in the list in the following way. Let me show you how this works. You can look it up on your own in the manual if you don't get this quickly. So let me define a little list here. It has to be a list of pairs. because pairs can have anything you want in them, but how about just three different pairs of integers here. So that's a little list, xs just looks like this. What a assoc does is it takes a number like three and a list of pairs and it checks the car fields of the pairs for something equal. And with the first time it finds one, it returns that pair. So assoc 3 xs returns 3, 4 assoc 1 xs returns 1, 2. And if it's not in the list, like six, you do see a six up here. But it only looks at the car fields, it returns false, meaning I did not find it in the list. So that's assoc. We're going to use assoc up here. So I had to tell you how it works. So our memo table which is initially null is going to be a list of pairs. And what it's going to be is argument.result. We're going to store in that list, pairs of, if Fibonacci of arg is result. All right, so here's what we do. If we find our answer in the table, so we got a pair here, and everything that's not false is true, so this works. And return the cdr of that pair. We looked up the argument x, we found it, returned the result. So that's how we get our reuse. In this else branch, we didn't find it. So now what we have to do is compute it, and then put it in the table so people can find it in the future. So how do we compute it? That's what this let variable does, new-ans. We say well if x is one or two, then it's one. Otherwise it's adding recursive callbacks minus one and recursive callbacks minus two. Before we return, change via set bang memo to hold a bigger list. Take the old list memo, cons onto it the pair of our new argument result pair. So then in the future if anyone needs Fibonacci of x they'll find it in the table. After we've done that, return this thing that we computed and that is the Fibonacci of the number. Is if this all works and what might surprise you is that it's fast. I can ask Fibonacci three of 1000 and I get this big number no time at all. So why is this so much efficient than the naive recursive version that couldn't even do 40? I don't even think it can do 35. It looks like if it's not in the table we're still doing these two recursive calls, and it would blow up exponentially. But we are doing two recursive calls whichever one we do second will be very, very fast. See the problem with exponential blowup is that we make two recursive calls, and they make two recursive calls. And they make two recursive calls, and it blows up two, four, eight, 16, 32. But what happens here, is we make two recursive calls. The first recursive call ends up filling up the table with lots of numbers. The second recursive call ends up finding what it needs in the table, especially if the second one is with x minus two. The second one is x minus one. It will still have to do one more recursive call, but then it will find what it needs in the table. And that's only at the top level. After that, everything's already in the table. So recursively at every step instead of making two expensive recursive calls, we make one recursive call. And then for the next recursive call everything is already in the table. So this isn't just twice as fast, it's twice as fast at every level. And in fact it's taking something that would take time proportional to two to the x and turning it in to something that takes time proportional to x. Or if you really want to be picky. Since I have to run down this list doing a soak. Maybe x squared. But x squared for 1000 is nothing. That's no problem at all. Whereas two to the x, where x is 1,000. Is more than I believe the number of particles in the universe. So that's our example, it's just a programming idiom. All we did was really something that had nothing to do with Fibonacci itself. We created this table, we always checked it first. If we found it we did nothing else otherwise we compute our answer and before we return, we add our result to the table, for the future. And that is memoization.