The Virtues of Laziness

It seems that I riled some people up with my blog post yesterday.  After some thought, I think the primary reason that there was some backlash is because some people feel that I violated one of the sacred principles of FP:  lists are *the* data structure.  Well, let me set the matter straight.  I love lists.  Especially the singlely linked immutable kind that are found in many functional languages.  Furthermore, Microsoft is not trying to launch some massive marketing campaign to sell IEnumerable<T> as the *new* list.  So to be clear, I talked about IEnumerable<T> yesterday because people who have used functional languages will wonder where are the lists in C# 3.0.  IEnumerable<T> is not the same as a list, but there are many similarities between IEnumerable<T> and lazy lists that I pointed out yesterday when I showed they are isomorphic by describing the bijective mapping between them.

Furthermore, it is the case that some data structures are generally better than others.  But there are tradeoffs between using the various data structures.  Also, *not* all of the tradeoffs are captured by looking exclusively at their time complexity for some operation.  There is of course the space complexity and there is the complexity of implementation itself.  And don't forget that often they have different characteristics for different operations.  The key point here is that a given problem will have a number of constraints and each of the competing designs has a number of trade-offs.  As an interviewer, when I notice a candidate is not aware of the trade-offs that he is making then I start to worry that they were not considered at all.  Furthermore, when I notice that a candidate seems to favor one data structure to the exclusion of others, I start to wonder how many tools are in the toolbox.  But after observing this behavior many times, I am convinced that it often is not the coding problem that is driving usage of some data structure but the mode of thinking that the candidate employs.

One more thing before I continue on.  At least one reader wondered why I said the following:

"Where most programmers who are accustomed to imperative style would naturally use an array, a variable, or a mutable object, a functional programmer will often use a list."

Yes, I meant to say exactly what I said.  In fact, when I wrote it, I paused before deciding to include it because I thought it might be misunderstood.  When I first read SICP, the most mind bending and rewarding topic was at the end of chapter 3.  The section on streams.  One of the motivations that was given for using a stream (infinite list) was that variables that change their value over time cause problems.  One way to address this was to have streams represent the state of the variable over time where each element of the stream represents a state of the variable at some point in time.

So without further ado, let's take a look at streams...

What we want is an infinite list.  The problem is that infinite list can never actually be fully realized because of their infinite nature.  So if we attempt to realize an infinite list either the computer will enter an infinite loop or it will run out of resources (stack overflow, out of memory, etc.).

We can overcome this problem by having lazy lists.  Lists where the next element in the list is not realized until it is needed.  Yesterday, I presented one such lazy list which uses an enumerator to realize the next element.  Today, I present another which has a more intriguing definition.

class Stream<T> : IList<T>
{
Func<IList<T>> next;
T value;

  public Stream(T value, Func<IList<T>> next)
{
this.value = value;
this.next = next;
}

  public IList<T> Next { get { return next(); } }
public T Value { get { return value; } }
}

This lazy list is very similar to a normal list.  The only difference is that instead of taking a list as the value of the next node in the list, it takes a function which will evaluate to the next node in the list.  But this difference is critical.

The first difference can easily be seen by imaging a list type, ErrorList, that when constructed throws an exception.

class ErrorList<T> : IList<T>
{
public ErrorList() { throw new Exception(); }
public IList<T> Next { get { throw new Exception(); } }
public T Value { get { throw new Exception(); } }
}

Now consider the following code:

var list = new List<int>(1, new ErrorList<int>()); // error, exception thrown
var stream = new Stream<int>(1, () => new ErrorList<int>()); // no error

An exception is thrown when the list is constructed but when the stream is constructed no exception is thrown.  Unless the Next property is evaluated on the stream, there will never be an exception.

The second difference can be seen in the following code:

IList<BigInteger> onesList = null;
onesList = new List<BigInteger>(1, onesList);
IList<BigInteger> onesStream = null;
onesStream = new Stream<BigInteger>(1, () => onesStream);

If you try to list all of the values in onesList, then you will notice that it only contains one value.  Whereas onesStream contains an infinite number of values.  The reason is that when we constructed onesList, we passed in onesList but onesList had the value null at the time so the next node was set to null.  But in the stream case we passed in a function that would be evaluated sometime in the future.  By the time that we evaluate it, it will return the proper value of onesStream.

A third difference is found in the performance of the two lists.  With the lazy lists, parts of the list that are never realized are never paid for.  So it is a pay as you go model as opposed to pay everything up front.  Furthermore, less space can be required since the whole list is not necessarily held in memory at once but only a process decription that can compute each element as it is required.

So now we have this infinite stream of ones, but can we do anything more interesting?  Sure.  First, let's define a zip function between lists.

  public static IList<V> Zip<T,U,V>(Func<T,U,V> f, IList<T> list1, IList<U> list2)
{
if (list1 == null || list2 == null)
return null;
return new Stream<V>(f(list1.Value, list2.Value), () => Zip<T,U,V>(f, list1.Next, list2.Next));
}

Yes, that is somewhat of a mouthful.  Here is what it does.  It takes two lists where the lists may differ from each other in what kind of elements they contain.  It also takes a function from the type of the first list's elements and the type of the second list's elements and returns possibly a new type.  Then if either of the lists is empty we return an empty list (null).  But if both lists are non-empty then we return a stream where the first element is the application of the given function to the first element of both of the lists and the rest of the list will be the evaluation of Zip on the rest of the two lists.  It is important that Zip uses a stream because these lists may be infinite and if we try to immediately evaluate the entire list we will run out of resources.

Now that we have Zip, let's put it to use to define the natural numbers.

IList<BigInteger> ones = null;
ones = new Stream<BigInteger>(1, () => ones);
IList<BigInteger> natural = null;
natural = new Stream<BigInteger>(0, () => Zip((x, y) => x + y, natural, ones));

So what we are saying is that the natural numbers begin with zero and then are followed by the sum of the first natural number with the first element of ones (0 + 1).  The second natural number is the sum of the second element of natural numbers with the second element of ones (1 + 1) and so on.  This works because each element of natural numbers is defined only in terms of the elements of natural numbers that occur previous to it.

So now we can easily define the odd numbers (2k + 1) and even numbers (2k).  But first we need a map function for lists.

public static IList<U> Map<T, U>(Func<T, U> f, IList<T> list)
{
if (list == null)
return null;
return new Stream<U>(f(list.Value), () => Map(f, list.Next));
}

Now here are the definitions of odd and even numbers.

IList<BigInteger> odds = Map(x => 2 * x + 1, natural);
IList<BigInteger> evens = Map(x => 2 * x, natural);

We can also define the fibonacci sequence as a stream.

IList<BigInteger> fibs = null;
fibs = new List<BigInteger>(0, new Stream<BigInteger>(1, () => Zip(add, fibs, fibs.Next)));

What we are saying here is that the first fibonacci number is zero and the second is one but then the next one is the sum of the first number and the second number and so on.  This is similar to the natural numbers definition which used itself to compute itself.

If you try it out, you will also notice that it isn't very efficient.  This is because we are back to our exponential time complexity.  But this can easily be remedied by memoizing the next function in the constructor to the stream:

  public Stream(T value, Func<IList<T>> next)
{
this.value = value;
this.next = next.Memoize();
}

Now it has linear time complexity by trading off some space (linear as well).

Let's finish by solving the famous problem of producing the Hamming numbers.  The problem is to list all of the positive integers who have no prime factors other than 2, 3, or 5 in ascending order.  The first ten Hamming numbers are:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12

This problem is notoriously difficult without lazy evaluation and is used to demonstrate the power of laziness.

To solve this problem first note that the first hamming number is 1.  Then if h is a hamming number so is 2h, 3h, and 5h.  So we can define three streams which map the hamming numbers to 2h, 3h, and 5h respectively.  The only remaining requirement is that they must be in order.  We can maintain this invariant by defining a function named Merge:

public static IList<T> Merge<T>(IList<T> list1, IList<T> list2) where T : IComparable<T>
{
if (list1 == null)
return list2;
else if (list2 == null)
return list1;
int c = list1.Value.CompareTo(list2.Value);
if (c < 0)
return new Stream<T>(list1.Value, () => Merge(list1.Next, list2));
else if (c > 0)
return new Stream<T>(list2.Value, () => Merge(list1, list2.Next));
else
return new Stream<T>(list1.Value, () => Merge(list1.Next, list2.Next));
}

Now we are ready to define the Hamming numbers.  Notice how close the definition in the code is to our description:

IList<BigInteger> hamming = null;
hamming = new Stream<BigInteger>(1, () => Merge(Map(x => x * 2, hamming), Merge(Map(x => x * 3, hamming), Map(x => x * 5, hamming))));

Now for fun, try to think of how to do it without lazy evaluation.