In my last post I talked about a Stream class for creating efficient lazy lists in C#.  In addition, I showed several classic functional methods I ported to C# to be used on the lazy lists.  As I mentioned in that post, I will now talk about an example I included in the [download id=”14″ format=”4″] for the lazy list class.

The example is an implementation of a naive sieve for generating prime numbers. This prime generator is a classic example of lazy list evaluation in Haskell.  This is the sieve in Haskell:

primes = sieve [2..]
sieve (p : xs) = p : sieve [x | x <- xs, x ‘mod‘ p > 0]

This sieve is often mistakenly called the Sieve of Eratosthenes.  This sieve behaves differently and is extremely less efficient.  An explanation on how the sieve above is different from the Sieve of Eratosthenes can be found in this paper by Melissa E. O’Neill.

Irregardless of the fact that this is not the Sieve of Eratosthenes it still exhibits the beauty of lazy lists.  Each invocation of the sieve method gets passed a new lazy list with a filter applied to it.  The filter excuted on a per element basis when it is needed on an element.  This code is really pretty and exhibits the idea of filtering an infinite stream and passing this filtered stream into another method to be filtered again.

With the stream class from my last post and some of the method I defined we can create this method in C# (although with out the same elegant syntax since we don’t have list comprehension).  My definition in C# is show below

Stream<int> naturals = null;
naturals = new Stream<int>(0, () => ones.ZipWith(naturals, (x, y) => x + y));
Stream<int> naturalsFromTwo = naturals.Tail.Tail;

Stream<int> primes = null;
primes = Primes(naturalsFromTwo);

// ... 

static Stream<int> Primes(Stream<int> xs)
{
    return new Stream<int>(xs.Head, () => Primes(xs.Tail.Filter(x => x % xs.Head != 0)));
}

While this code looks much uglier it is doing the same thing.  First of all, naturals, is a stream which is all the natural numbers.  I then create naturalsFromTwo which is the same as [2..] which you saw in the Haskell code.  The Primes function is the same as the sieve function in the Haskell code.  It takes a stream and creates a new stream with all of the next primes multiples filtered out of it.

Beautiful!