[MUSIC] So now that we know how to use streams, I want to show you how you can define your own. Which is usually what you need to do first before you can use them, but I put it off in order to present things in the other order. Remember that what we are a calling a stream is a thunk that when you call it returns a pair of the first element of the stream, and then a stream for the rest of the other elements. The infinitely many that follow. So now what we want to do is make our own. I admit this is a little mind-bending but it just uses things we already know. So just understand where we're using recursion, where we're using funking and it's all just going to work out surprisingly easily. It's one of those things where the code is so short you think it's simpler than it actually is. And that will be fine, okay? So let's just do this. And for the first stream I want to generate, let's do the simplest thing in the world. It's a stream that no matter how many times you call it, it just returns one forever. It's the infinite sequence of ones. So I'll just define a variable to hold my stream and I'll call it ones. So every stream is a thunk, so this is what my thunk is going to be. So when I call this thunk, I need to return a pair. Do that with cons. The first thing should be one, and now what I need here is a stream that returns all ones. So what you could think is that, well, that needs to be a thunk, right? And that's going to have to return a pair. And then that's going to need another thunk. And that's going to have to return a pair and we're going to be here literally forever if you try to define your stream that way. But we can do something better. Right here, where I was, I need to put right here something that is a thunk that when called returns a pair of 1 and then a thunk with more ones. And I actually have just the thing I need. All right, so this looks like I'm defining ones in terms of ones, and I am. Every recursive function is on some level defined in terms of itself. This make perfect sense. Ones will be bound to a thunk that when you call it returns a pair of one and then the procedure itself. It's just recursion, just in a different way than you've seen it before. This really does produce the stream, but let me show you if I call ones and take the car of that. Excuse me here, car of that. I will get a 1 and if I take the cdr of it and call that to get a pair back and take the car of that, I get another 1 and so on forever, okay? So that's ones. Now let's do a more interesting one, slightly more interesting, we're building up of course. 1, 2, 3, 4, 5. Something that is the stream of the natural numbers. The positive integers, okay? I'm going to define a function f that's going to take one argument. We'll return the stream that starts at x, all right? So it'll do x, x + 1, x + 2 forever. So what I do for that one is I just need to return, let's see a pair. Well, the way I'm going to do it, is I'm going to say if you give me x, I'll give you back a pair of x. So I'm not returning a stream here, I'm returning the pair. But then the thing in the cdr will be the infinite sequence that starts at x = 1, and goes on forever. And again, we see recursion. That if you call f with a number x, you get back a pair of x. And a thunk, that when you call it, will give back a pair of x + 1 and a thunk that when you call it and so on. And now all I need for nats is a lambda, a thunk, that when you call it, because every steam is a thunk. So the stream of natural numbers is just a thunk that then just calls f with 1, okay? So this works fine. The way I would prefer to do it. Let me just make a copy real fast. Is since f is really a helper function, I'd rather I define it as such. Cons x (lambda thunk (f + x 1). And then lambda f 1. And that's just slightly better style. So that's all fine. We could test that one out as well. How about the one I showed you in the previous segment, powers of 2. That goes 2 4 8 16 and so on. We saw it grew very fast. It turns out it's a whole lot like nats. It's so much like nat that I'm going to copy and paste it and say powers of two, all right? And all I need to do is instead of adding one, I need to multiply by two. And we'll get it over there. There we go, all right. And of course, I should've spelled lambda correctly. And of course, the code posted with the segment will be absolutely correct, in case I'm making any typos here. And now I have my stream powers of two. And of course, and you just saw that sort of copy and paste, I really shouldn't do that sort of thing. Instead I should have helper functions, right? So maybe a helper function could be called stream-maker, and it could take in a function for combining things. And the argument that is the previous one, and I'm going to leave this to you if you're curious to look up in the code that I'll post with this lecture. How to define this, it's really just subtracting over the fact that I have a plus one here and a times two there. And then I define a version of nats where I just call stream-maker with the addition function in one. And a version of powers-of-two where I call stream-maker with multiply and 2. But instead of showing the details of that, I'd rather emphasize the basic idea of what these streams are doing. That in every case, right, every stream is a thunk, that when you call it returns a pair, all right? And the way it knows the hard part of that pair, is the cdr, the next thunk, right? And the body of that thunk ends up being something that uses recursion. So in nats, the body of that thunk, which we don't call right away, just calls f again with x + 1. In the ones case, we just got to use the function itself. It would look more like the other ones if we said lambda no arguments call ones. And that's totally correct, it's just unnecessary function wrapping. What's the point of having a thunk that when you call it calls ones with no arguments? Ones is just as good. So the other thing I want to emphasize for you, because it is mind-bending and difficult to define your own streams, is some mistakes you might make. So let's do that in terms of ones. So here's a couple things that if you understand why these don't work, you may be in a better position to understand why the version above does work. So here's one that's just really-bad. It just returns cons of 1, and ones-really-bad, okay? So first of all, it's not returning a thunk at all, it's returning a pair. And to evaluate a pair, we need to look up ones-really-bad but we're not even done defining it. This doesn't work in a language like Racket because it's an eager language. When you go to evaluate this binding for ones-really-bad, we need to evaluate this pair. And to evaluate this pair, we need to look up this variable then we're not done defining it. That really is circular. Something like this does work in Haskell, if you've seen it, exactly because the semantics of function call for cons is different in Haskell. It definitely does not work in a language like Racket or ML or Java or any of the other languages with eager semantics for function calls. So that one definitely doesn't work. This one might frustrate you a little bit more if you do something like this. So, I return a thunk. That's great, all right? And now I think, well, I need to cons one onto something, and now what I want to do is call this thunk, ones-bad. So I can do that. Because now my recursion is inside this function. So it is a recursive function call. But what this does, it does not put a thunk in the cdr. It puts the results of calling that thunk, and in its cdr will be the result of calling that thunk. And in its cdr will be the result of calling that thunk. And this is an infinite loop. This is something that if you evaluate ones-bad, so if I click run here, oop, can't define things multiple times in a module. So let's delete all this down here, and then come back up here and try it again. Everything worked fine. Ones-bad is a thunk, right? It's a procedure but as soon as I call it, it's going to generate a list that's infinitely long. And that's not what streams are. I'm going to have to click Stop up here. Streams are not things that are infinitely long. They are things that, when you keep applying the thunks and the cdr, you can keep getting additional values. That's why the version above is correct and the version bad just creates an infinite loop. So, that's defining streams. On your homework, you'll get to define a stream. You'll also define a function that takes a stream and returns a new stream. That's something I didn't show you. It'll be a challenge for you, even though you need to do it. To just take the steps we've seen, get the idea of right where you have a thunk, where you need to call a thunk. And then you can program it with streams. You'll be able to test them out by using streams and you've learned a powerful and subtle programming idiom.
