The Lazy functor by Mark Seemann
Lazy evaluation forms a functor. An article for object-oriented programmers.
This article is an instalment in an article series about functors. Previous articles have covered Maybe, rose trees, and other functors. This article provides another example.
Most programming languages are eagerly evaluated. Sometimes, however, you'd like to defer execution of an expensive operation. On .NET, you can use Lazy<T> to achieve that goal. This generic type, like so many others, forms a functor.
Functor #
You can implement an idiomatic Select extension method for Lazy<T> like this:
public static Lazy<TResult> Select<T, TResult>( this Lazy<T> source, Func<T, TResult> selector) { return new Lazy<TResult>(() => selector(source.Value)); }
This would, for example, enable you to write code like this:
Lazy<int> x = // ... Lazy<string> y = x.Select(i => i.ToString());
Or, using query syntax:
Lazy<int> x = // ... Lazy<string> y = from i in x select i.ToString();
You can add more steps to such a pipeline of lazy computation until you finally decide to force evaluation with the Value property.
Notice that while the Select method looks like it might force evaluation as well, by accessing the Value property, this happens inside a new lazily evaluated lambda expression. Thus, all steps in a Lazy pipeline are deferred until evaluation is forced.
First functor law #
The Select method obeys the first functor law. As usual in this article series, actually proving that this is the case belongs in the realm of computer science. Instead of proving that the law holds, you can demonstrate that it does using property-based testing. The following example shows a single property written with FsCheck 2.11.0 and xUnit.net 2.4.0.
[Property(QuietOnSuccess = true)] public void LazyObeysFirstFunctorLaw(int i) { var left = Lazy.FromValue(i); var right = Lazy.FromValue(i).Select(x => x); Assert.Equal(left.Value, right.Value); }
Even though you may feel that a property-based test gives you more confidence than a few hard-coded examples, such a test is nothing but a demonstration of the first functor law. It's no proof, and it only demonstrates that the law holds for Lazy<int>, not that it holds for Lazy<string>, Lazy<Address>, etcetera.
Both this property and the next uses this little static helper method:
public static Lazy<T> FromValue<T>(T value) { return new Lazy<T>(() => value); }
This helper method is only a convenience. You can put in a delay if you want to pretend that actual lazy evaluation takes place. It'll make the tests run slower, but otherwise will not affect the outcome.
Second functor law #
As is the case with the first functor law, you can also use a property to demonstrate that the second functor law holds:
[Property(QuietOnSuccess = true)] public void LazyObeysSecondFunctorLaw( Func<string, byte> f, Func<int, string> g, int i) { var left = Lazy.FromValue(i).Select(g).Select(f); var right = Lazy.FromValue(i).Select(x => f(g(x))); Assert.Equal(left.Value, right.Value); }
Again the same admonitions apply: that property is no proof. It does show, however, that given two functions, f and g, it doesn't matter if you map a Lazy computation in one or two steps. The output is the same in both cases.
F# #
F# has built-in language support for lazy evaluations, but surprisingly doesn't supply a map function. You can, however, easily implement such a function yourself:
module Lazy = // ('a -> 'b) -> Lazy<'a> -> Lazy<'b> let map f (x : Lazy<'a>) = lazy f x.Value
This enables you to write code like this:
let (x : Lazy<int>) = // ... let (y : Lazy<string>) = x |> Lazy.map string
The F# language feature is based on the same Lazy<T> class that you can use from C# (and Visual Basic .NET), so the behaviour is the same as described above. The functor laws hold for the Lazy.map function just like it holds for the above Select method.
Haskell #
Unlinke C#, F#, and most other programming languages, Haskell is lazily evaluated. All values, whether scalar or complex, are lazy by default. For that reason, there's no explicit Lazy type in Haskell.
Haskell values are, in themselves, not functors, but you can put any value into the Identity functor. Since all values are already lazy, you could view Identity as Haskell's Lazy functor.
The equivalence is only partial, however. .NET Lazy objects are small state machines. Before you've forced evaluation, they carry around the expression to be evaluated. Once you've evaluated the value once, Lazy objects effectively replace the lazy expression with its result. Thus, the next time you access the Value property, you immediately receive the result.
Haskell's lazily evaluated values are different. Since they're immutable, they don't 'change state' like that. On the other hand, sometimes the Haskell compiler can identify optimisations that it can apply to make lazily evaluated values more efficient. In other cases, you may have to apply more explicit memoisation.
Summary #
In languages with eager evaluation (which is most of them), you can model deferred execution as a functor. This enables you to compose lazily evaluated expressions piecemeal.
Next: Asynchronous functors.
