The Lazy monad by Mark Seemann
Lazy computations form a monad. An article for object-oriented programmers.
This article is an instalment in an article series about monads. A previous article described how lazy computations form a functor. In this article, you'll see that lazy computations also form a monad.
SelectMany #
A monad must define either a bind or join function. In C#, monadic bind is called SelectMany. You can define one as an extension method on the Lazy<T> class:
public static Lazy<TResult> SelectMany<T, TResult>( this Lazy<T> source, Func<T, Lazy<TResult>> selector) { return new Lazy<TResult>(() => selector(source.Value).Value); }
While the implementation seemingly forces evaluation by accessing the Value property, this all happens inside a lambda expression that defers execution.
If x is a Lazy<int> and SlowToString is a function that takes an int as input and returns a Lazy<string> you can compose them like this:
Lazy<string> y = x.SelectMany(SlowToString);
The result is another lazy computation that, when forced, will produce a string.
Query syntax #
Monads also enable query syntax in C# (just like they enable other kinds of syntactic sugar in languages like F# and Haskell). As outlined in the monad introduction, however, you must add a special SelectMany overload:
public static Lazy<TResult> SelectMany<T, U, TResult>( this Lazy<T> source, Func<T, Lazy<U>> k, Func<T, U, TResult> s) { return source.SelectMany(x => k(x).Select(y => s(x, y))); }
This would enable you to rewrite the above example like this:
Lazy<string> y = from i in x from s in SlowToString(i) select s;
The behaviour is the same as above. It's just two different ways of writing the same expression. The C# compiler desugars the query-syntax expression to one that composes with SelectMany.
Flatten #
In the introduction you learned that if you have a Flatten or Join function, you can implement SelectMany, and the other way around. Since we've already defined SelectMany for Lazy<T>, we can use that to implement Flatten. In this article I use the name Flatten rather than Join. This is an arbitrary choice that doesn't impact behaviour. Perhaps you find it confusing that I'm inconsistent, but I do it in order to demonstrate that the behaviour is the same even if the name is different.
The concept of a monad is universal, but the names used to describe its components differ from language to language. What C# calls SelectMany, Scala calls flatMap, and what Haskell calls join, other languages may call Flatten.
You can always implement Flatten by using SelectMany with the identity function.
public static Lazy<T> Flatten<T>(this Lazy<Lazy<T>> source) { return source.SelectMany(x => x); }
You could also compose the above x and SlowToString with Select and Flatten, like this:
Lazy<Lazy<string>> nested = x.Select(SlowToString); Lazy<string> flattened = nested.Flatten();
The flattened value remains deferred until you force execution.
Return #
Apart from monadic bind, a monad must also define a way to put a normal value into the monad. Conceptually, I call this function return (because that's the name that Haskell uses). You don't, however, have to define a static method called Return. What's of importance is that the capability exists. For Lazy<T> in C# the idiomatic way would be to use a constructor, but the version of .NET I'm using for this code (this is actually code I wrote years ago) doesn't have such a constructor (newer versions do). Instead, I'll define a function:
public static Lazy<T> Return<T>(T x) { return new Lazy<T>(() => x); }
In other words, Return wraps a pre-existing value in a lazy computation.
Left identity #
We need to identify the return function in order to examine the monad laws. Now that this is done, let's see what the laws look like for the Lazy monad, starting with the left identity law.
[Property(QuietOnSuccess = true)] public void LazyHasLeftIdentity(Func<int, string> h_, int a) { Func<int, Lazy<int>> @return = Lazy.Return; Lazy<string> h(int x) => Lazy.Return(h_(x)); Assert.Equal(@return(a).SelectMany(h).Value, h(a).Value); }
Like in the previous article the test uses FsCheck 2.11.0 and xUnit.net 2.4.0. FScheck can generate arbitrary functions in addition to arbitrary values, but it unfortunately, it can't generate lazy computations. Instead, I've asked FsCheck to generate a function that I then convert to a lazy computation.
In order to compare the values, the assertion has to force evaluation by reading the Value properties.
Right identity #
In a similar manner, we can showcase the right identity law as a test.
[Property(QuietOnSuccess = true)] public void LazyHasRightIdentity(Func<string, int> f_, string a) { Func<string, Lazy<int>> f = x => Lazy.Return(f_(x)); Func<int, Lazy<int>> @return = Lazy.Return; Lazy<int> m = f(a); Assert.Equal(m.SelectMany(@return).Value, m.Value); }
As always, even a property-based test constitutes no proof that the law holds. I show it only to illustrate what the laws look like in 'real' code.
Associativity #
The last monad law is the associativity law that describes how (at least) three functions compose.
[Property(QuietOnSuccess = true)] public void LazyIsAssociative( Func<int, string> f_, Func<string, byte> g_, Func<byte, TimeSpan> h_, int a) { Lazy<string> f(int x) => Lazy.Return(f_(x)); Lazy<byte> g(string x) => Lazy.Return(g_(x)); Lazy<TimeSpan> h(byte x) => Lazy.Return(h_(x)); Lazy<string> m = f(a); Assert.Equal(m.SelectMany(g).SelectMany(h).Value, m.SelectMany(x => g(x).SelectMany(h)).Value); }
This property once more relies on FsCheck's ability to generate arbitrary pure functions, which it then converts to lazy computations.
Conclusion #
The Lazy functor (which is also an applicative functor) is also a monad. This can be used to combine multiple lazily computed values into a single lazily computed value.
Next: Asynchronous monads.
