I had the thought—while browsing through some old code—that the code I used to implement futures in C# would be useful for doing things lazily, if you just moved the evaluation phase to when the value was actually demanded… this started me off thinking about how to implement a proper lazily-evaluated list in C#.
A first attempt
The first thing I thought of was to implement them using an IEnumerable with yield statements, so I began with a construction borrowed from Haskell: the iterate function.
static class FakeLazyList { public static IEnumerable<T> Iterate<T>(Func<T, T> f, T x) { while (true) { yield return x; x = f(x); } } }
While this works (try FakeLazyList.Iterate(i => i + 1, 0)), it is obviously a poor solution; it is not flexible as it requires a seperate function to be written for every incarnation.
Lazy data in general
My next approach was to begin with creating a generic type for lazy data. All it has to do is act as a wrapper for a piece of data. However, since in C# arguments must be evaluated before they are used, the data must in turn be wrapped inside a delegate so that the delegate’s execution can be postponed. This resulted in:
public class Lazy<T> { public Lazy(Func<T> del) { Del = del; } private Func<T> Del; private T PValue; private bool HasValue = false; public static implicit operator T(Lazy<T> f) { if (!f.HasValue) { f.PValue = f.Del.Invoke(); f.HasValue = true; } return f.PValue; } }
As you can see, execution of the data-bearing delegate is delayed until the lazy data is forced to become normal data.
Implementing the list
For the list implementation itself, I chose to go with the traditional cons list structure, so that each list item has an object of data, and a pointer to the next item in the list. In order to make the list lazy, the next item of the list should be generated only on-access, so it is wrapped in the above Lazy<T> class.
public class LazyList<T> : IEnumerable<T>, IEnumerable { private T _First; private Lazy<LazyList<T>> _Rest; public T First { get { return _First; } } public LazyList<T> Rest { get { return _Rest; } } public LazyList(T first, Lazy<LazyList<T>> rest) { _First = first; _Rest = rest; }
Next comes some boilerplate so that the class can be used as an enumerable structure:
public IEnumerator<T> GetEnumerator() { return new Enumerator(this); } IEnumerator IEnumerable.GetEnumerator() { return new Enumerator(this); } private class Enumerator : IEnumerator<T>, IEnumerator { private LazyList<T> curr = null; private LazyList<T> next; public Enumerator(LazyList<T> parent) { next = parent; } /* must implement both interfaces */ object IEnumerator.Current { get { return this.Current; } } public T Current { get { if (curr == null) throw new InvalidOperationException(); else return curr._First; } } public bool MoveNext() { curr = next; next = next._Rest; return curr != null; } public void Reset() { throw new NotSupportedException(); } public void Dispose() { return; } }
Last of all comes a couple of utility functions for constructing lists, both of which I took from Haskell. The first, iterate, generates a list of items by taking a function f and a datum x and generating the list like this [x,f(x),f(f(x)),f(f(f(x))),...].
public static LazyList<X> Iterate<X>(Func<X, X> f, X x) { return new LazyList<X>(x, new Lazy<LazyList<X>>(delegate { return Iterate(f, f(x)); })); }
The next takes a datum and generates the infinite list of just that datum:
public static LazyList<X> Repeat<X>(X x) { return new LazyList<X>(x, new Lazy<LazyList<X>>(delegate { return Repeat(x); })); } }
As you can see, the usage of the LazyList constructor isn’t the most elegant. I had hoped that I would be able to use an implicit operator on the Lazy class, such as:
public static implicit operator Lazy<T>(Func<T> f) { return new Lazy<T>(f); }
… and then use it like this …
new LazyList<X>(x, () => Repeat(x));
Unfortunately, this doesn’t work, giving error CS1660. Apparently the C# compiler cannot use the fact that an implicit cast has been defined. Still, this implementation works well.
Usage
The usage of the LazyList in normal code is very simple, and as shown in this example, you can also use the new C# 3.0-defined list operators Take, Drop, Where etc:
IEnumerable<int> ys; // Lazy list of all positive integers ys = LazyList<int>.Iterate(i => i + 1, 0).Take(20); foreach (var y in ys) Console.WriteLine(y); //Lazy list of [89, 89, 89, 89, ...] ys = LazyList<int>.Repeat(89).Take(20); foreach (var y in ys) Console.WriteLine(y); Console.ReadLine();
Post a Comment