Digging deeper into C# Lazy Lists

One of the most interesting aspects of the Haskell language is the fact that features lazy evaluation.  My interest in lazy evaluation led me to a post on Wes Dyers blog about lazy lists in C#.  In his blog post he talks describes how to create a lazy list class in C# and demonstrates some classic lazy and functional methods of manipulating them.  After reading this I decided to use his code as a basis to some further experimentation.

I started playing with his code and modifying it to make it easier to use.  The end result was a class and a set of methods which allow you to easily use and manipulate lazy lists in C#. I will list some changes/ additions I made below:

Stream Class

I first changed the names next  and value from Wes's example to head and tail since I feel that makes more sense.

I then modified the stream class to implement IEnumerable<T>.  This will allow the stream to be used more seamlessly in code and act just as any other collection does.  The implementation for GetEnumerator was pretty straight forward:

 public IEnumerator<T> GetEnumerator()
{
    yield return head;

    var t = tail();
    if (t != null)
    {
        foreach (var x in t)
            yield return x;
    }

}

The third change I made to the Stream class was to not use his Memoize method but to add another field in the stream class called realized which will store the value of tail after its first use.  I felt this was easier to read.

Lazy List Functions

In Wes's post he shows how to implement Zip (well he actually showed ZipWith but called it Zip) and Map on the stream class.  I added to this by first converting them to extension methods just for convenience.  Then I added many other methods over lists that any functional programmer is used to having like:

Fold

 public static T FoldR<U, T>(this Stream<U> st1, Func<U, T, T> folder, T init)
{
    if (st1 == null) return init;
    if (st1 != null && st1.Tail == null) return folder(st1.Head, init);
    return folder(st1.Head, st1.Tail.FoldR(folder, init));
}

public static T FoldL<U, T>(this Stream<U> st1, Func<T, U, T> folder, T init)
{
    if (st1 == null) return init;
    return st1.Tail.FoldL(folder, folder(init, st1.Head));
}

and

Filter

 public static Stream<T> Filter<T>(this Stream<T> st1, Func<T, bool> filter)
{
    if (st1 == null) return null;
    if (filter(st1.Head))
        return new Stream<T>(st1.Head, () => st1.Tail.Filter(filter));
    else
        return st1.Tail.Filter(filter);
}

Then to top it all off I added an extension method AsStream to allow you as convert any IEnumerable into a Stream:

 public static Stream<T> AsStream<T>(this IEnumerable<T> coll)
{
    return coll.GetEnumerator().AsStream();
}

public static Stream<T> AsStream<T>(this IEnumerator<T> enumer)
{
    if (enumer.MoveNext())
    {
        return new Stream<T>(enumer.Current, () => enumer.AsStream());
    }
    else
    {
        return null;
    }
}

With all of these extension methods you will now be able to take a running start at Lazy Lists in C#.

I posted the code I worked on on Code Gallery so click here if you want to download it an give it a spin.

The code contains several examples of using the stream class and also a lazy prime generator which I will discuss in my next post.