, I wanted 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 it's still worth knowing and it's 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 it's been called that for a long time. So here's the idea, if a function has no side effects and doesn't read anything that can change. There's no point in computing it twice for the same argument. If you call it twice with seven you're going to get the same answer. If you call it twice with the same lists you're going to get the same answer. Doesn't matter how many times you call it. So what we could do is keep what's called a cache of previous results. Keep some data structure that remembers. Hey if you call this funciton with seven, this is what you're going to get back. And this can be a great idea if maintaining and using the cash is cheaper. Then recomputing the results. And if people actually do the recomputations. They actualy call the same function with the same argument again. Otherwise, the cache is a waste of space and a waste of time. So, this idea is really pretty similiar to promises. That thing we saw with force and delay, right? That when we do the first force, we'll store the result so any later force just has the result there. But force of delay was for thunks that don't take any arguments. Once you take arguments, you can't just have one thing that you've stored 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 and 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 could actually lead to programs that are much more efficient. other times, the y'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 from memoizaton, this is what most people use. Here's an implmentation the fibonacci function. This is a function for mathematics the same way we've been using factorial, which says that the factorial n is n times factorial of n minus 1. With a base case of factorial 0 as 1. Fibonacci is a little more sophisticated. It says fibonacci is one for both 1 and 2. So just read the racket code here. If x is one or x is 2, it's 1. Otherwise it's the sum of fibonacci of x minus 1. And Fibonacci of x minus 2. So you see two recursive calls here. And turns out these two recursive calls cause this to be a very inefficient implementation. This is exactly how it's defined mathematically. You recall Fibonacci 1 with 30 you get a nice big number like 830,000. But if you call with 40, this takes about a thousand times longer to evaluate. And I don't have a thousand 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? One thing you could 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 2 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 exists before moving on and showing you a different way to do this efficiently that show this idea of memoization. 'Kay, 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 that it's just implementing this idea of keeping around all the previous results. So, any time we compute Fibonacci of anything we're going to put that in our table. And because we're going to do that even when we make recursive calls it's going to in turn Fibonacci into an effecient. Function. So let's see how that works. So the first thing that 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 that I need f to use this memo table, this cash, this thing that is initially null but is bound to this variable memo. It's essential, I don't want memo to be at the top level, I don't want to define memo up here, 'cause 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'm going to define. 'Cause 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 next. And it's initially null. Now, we're going to use mutation to update it appropriately. Really. Okay, so when we want ca, find fibonacci of x, so we just call x right here, okay? 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 could have anything you want in them, but how about just, three different pairs of integers here. Okay. So that's a little list, xs just looks like this. What assoc does is it takes a number like 3. 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 pai r. So a assoc 3 xs returns 3, 4. Assoc 1 xs returns 1, 2 and if it's not in the list, like 6 you do see a 6 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 dot result. We're going to store in that list pairs of, if fibonacci, fibonacci of arg is result. Alright? So here's what we do. If we find our answer in the table, so we gotta pair here, and everything that is not false is true, so this works, and return the cdr of that pair. We looked up the argument x, we found it, return the result. So that's how we get our reels. In this else branch, we didn't find it. So now all 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 1 or 2, then it's 1. Otherwise it's adding recursive call of x minus 1 and recursive call of x minus 2. Before we return, change via set! memo to hold a bigger list. Take the old list memo, cons on to it the pair of our new argument result pair. So that 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. So, this all works and what might surprise you is that it's fast. I can ask fibonacci 3 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 could 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 m ake two recursive calls, and they make two recursive calls, and it blow ups, blows up 2, 4, 8, 16 and 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 2. The second one is x minus 1. 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 recursivly, 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 2 to the x. And turning it 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 assoc, maybe x squared. But x squared for a 1000 is nothing. that's no problem at all. Whereas, 2 to the x, where x is a 1000, 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 that something that had nothing 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.
