# Streams

These SICP lectures are great I tell ya! The two lectures on Streams (6a/6b) talk about implementing things with lazy lists. His examples are in Scheme but here’s my translation to C# using some of the new features in 3.0. For example, here is a lazy list of all integers starting with n:

public static IEnumerable<int> Integers(int n) {
while (true)
yield return n++; }

Cool, eh? (That can be done in 2.0 actually but we're getting to the good stuff...) It’s a bit strange to think of this as essentially an infinitely long List<int>, but why not? What I got out of the lectures was the idea that rather than think of variables changing over time, we can think of lazy lists as representing the complete set of values - fixed in time. Abelson said something funny about it: you can think of the values all being there in the same way that you think of your money being in your bank account – at least it’s there when you go to look for it and that’s all you should care about.

Wait a minute though, that code is using mutation! Well, sure it could be implemented as something like…

public static IEnumerable<int> Integers(int n) {
yield return n;
foreach (int i in Integers(n + 1))
yield return i; }

… but that’s quite a bit less efficient and the former is very well contained mutation. I’m not a pure functional zealot!

So what can we do with an infinitely long list of ints anyway? Certainly we can’t just foreach over all of them. That would be a ‘run on the bank!’ With some of the new extension methods hanging off of IEnumerable we can do things like Integers(1).Take(10) to get 1-10 or we can filter (Where()) or map (Select()) or reduce (Aggregate()) them. How ’bout the good ol’ factorial function using our Integers stream this time:

public static int Factorial(int n) {
return Integers(1).Take(n).Aggregate(1, (a, b) => a * b); }

Pretty simple. It works by taking the first n integers and multiplying them all together (the (a,b)=>a*b lambda expression) seeded with 1.

How about a lazy list of Fibonacci numbers using recursion:

public static IEnumerable<int> Fibs(int a, int b) {
yield return a;
foreach (int i in Fibs(b, a + b))
yield return i; }

Fun! Now we can say var fibs = Fibs(0, 1); and get, what can be thought of as, the complete list of Fibonacci numbers. To try it out, we can add a Print() method to IEnumerable (extension methods are such a cool feature).

public static void Print(this IEnumerable<int> list) {
foreach (int i in list)
Console.Write("{0}, ", i);
Console.WriteLine(); }

So now we can say fibs.Take(20).Print(); and get 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181. Nifty.

Here’s the finale. Everyone knows the Sieve of Eratosthenes for finding prime numbers. The usual way of implementing it is to cross off non-primes in a giant bit array or something like that. I remember when we first got our 64-bit dev boxes with 8GB of RAM on the Search team. The first thing Dan and I did was to calculate all the primes between 1 and 100-billion using up more memory for the bit array (of only odd numbers) than is even addressable in 32-bits.

Here is a very elegant (though much less performant) way to do it with streams:

public static IEnumerable<int> Sieve(this IEnumerable<int> list) {
int first = list.First();
yield return first;
foreach (int j in list.Where(x => x % first != 0).Sieve())
yield return j; }

For the given list of integers (it's an extension method of IEnumerable<int>), it returns the first element followed by the rest of the list filtered down to only those that are not divisible by the first (using the Where() extension method - the same one corresponding to the Linq keyword ‘where’ - and using a lambda expression for non-divisibility).

So, for example, a list of ints starting with 2, 3, 4, 5, 6, 7, … would return 2 followed by only odd numbers 3, 5, 7, … But notice that the filtered list is recursively run through Sieve() which will return, of the list of ints not divisible by 2, the ones that are also not divisible by 3, and of those the ones not divisible by 5, then filtered again by 7, and 11, etc. This is the Sieve of Eratosthenes in just a few lines. Absolutely beautiful! To kick it off, we just say:

var primes = Integers(2).Sieve();

… and voila! We have a lazy list of all primes. We can now say:

Console.WriteLine(primes.ElementAt(20));

… and out comes 73. Or we can say:

primes.Take(100).Print();

… and get 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541,

We can now think of the range of a function, not as the result of computation, but as if it were just plain data; slick concept!