Example of lazy evaluation

Chris Okasaki has the following example in his book of lazy evaluation: $-notation

$ is a constructor for a new datatype called a suspension. In other words: datatype 'a suspension = $ of 'a

the constructor $ takes an argument that is an expression to evaluate at a later time. In order to do this it needs to store a code pointer along with the free variables used in the expression. As you can see, this is very similar to an anonymous delegate. An anonymous delegate gives you the code pointer, and the compiler takes all the captured variables and produces a class (similar to a closure) to hold it for you without having to do that explicit work yourself.

In SML we could do the following:

val s = $(primes 1000000)

val $x = s

val $y = s

The first line is very fast because it just creates the new suspension. The second line will be slow as the 1 millionth prime is computed. The third line will be fast because we'll just return the memoized value.

Using C# we could write this as:

Creator<int> s = LazyCreator.Create<int>(delegate { return primes(1000000); });

int x = s();

int y = s();

For the most part it's as simple as the functional equivalent. Except that the syntactic sugar of $ is very very nice. 1 character versus around 35. I'll have to see if we can do something a little better (maybe better names and some use of operator overloading). Or maybe it isn't a big deal being so explicit.