The Marvels of Monads


If the word "continuation" causes eyes to glaze over, then the word "monad" induces mental paralysis.  Perhaps, this is why some have begun inventing more benign names for monads.

These days, monads are the celebrities of programming language theory.  They gloss the cover of blogs and have been compared to everything from boxes of fruit to love affairs.  Nerds everywhere are exclaiming that the experience of understanding monads causes a pleasantly painful mental sensation.

Like continuations, monads are simpler than they sound and are very useful in many situations.  In fact, programmers write code in a variety of languages that implicitly use common monads without even breaking a sweat.

With all of the attention that monads get, why am I writing yet another explanation of monads?  Not to compare them to some everyday occurrence or to chronicle my journey to understanding.  I explain monads because I need monads.  They elegantly solve programming problems in a number of languages and contexts.

Introducing Monads

Monads come from category theoryMoggi introduced them to computer scientists to aid in the analysis of the semantics of computations.  In an excellent paper, The Essence of Functional Programming, Wadler showed that monads are generally useful in computer programs to compose together functions which operate on amplified values rather than values.  Monads became an important part of the programming language Haskell where they tackle the awkward squad: IO, concurrency, exceptions, and foreign-function calls.

Monads enjoy tremendous success in Haskell, but like an actor who does well in a particular role, monads are now stereotyped in the minds of most programmers as useful only in pure lazy functional languages.  This is unfortunate, because monads are more broadly applicable.

Controlling Complexity

Composition is the key to controlling complexity in software.  In The Structure and Interpretation of Computer Programs, Abelson and Sussman argue that composition beautifully expresses complex systems from simple patterns.

In our study of program design, we have seen that expert programmers control the complexity of their designs with the same general techniques used by designers of all complex systems. They combine primitive elements to form compound objects, they abstract compound objects to form higher-level building blocks, and they preserve modularity by adopting appropriate large-scale views of system structure.

One form of composition, function composition, succinctly describes the dependencies between function calls.  Function composition takes two functions and plumbs the result from the second function into the input of the first function, thereby forming one function.

public static Func<T, V> Compose<T, U, V>(this Func<U, V> f, Func<T, U> g)
{
    return x => f(g(x));
}

For example, instead of applying g to the value x and then applying f to the result, compose f with g and then apply the result to the value x.  The key difference is the abstraction of the dependency between f and g.

var r = f(g(x));         // without function composition
var r = f.Compose(g)(x); // with function composition

Given the function Identity, function composition must obey three laws.

public static T Identity<T>(this T value)
{
    return value;
}

1.  Left identity

     Identity.Compose(f) = f

2.  Right identity

     f.Compose(Identity) = f

3.  Associative

     f.Compose(g.Compose(h)) = (f.Compose(g)).Compose(h)

Often, values are not enough.  Constructed types amplify values.  The type IEnumerable<T> represents a lazily computed list of values of type T.  The type Nullable<T> represents a possibly missing value of type T.  The type Func<Func<T, Answer>, Answer> represents a function, which returns an Answer given a continuation, which takes a T and returns an Answer.  Each of these types amplifies the type T.

Suppose that instead of composing functions which return values, we compose functions which take values and return amplified values.  Let M<T> denote the type of the amplified values.

public static Func<T, M<V>> Compose<T, U, V>(this Func<U, M<V>> f, Func<T, M<U>> g)
{
    return x => f(g(x)); // error, g(x) returns M<U> and f takes U
}

Function composition fails, because the return and input types do not match.  Composition with amplified values requires a function that accesses the underlying value and feeds it to the next function.  Call that function "Bind" and use it to define function composition.

public static Func<T, M<V>> Compose<T, U, V>(this Func<U, M<V>> f, Func<T, M<U>> g)
{
    return x => Bind(g(x), f);
}

The input and output types determine the signature of Bind.  Therefore, Bind takes an amplified value, M<U>, and a function from U  to M<V>, and returns an amplified value, M<V>.

public static M<V> Bind<U, V>(this M<U> m, Func<U, M<V>> k)

The body of Bind depends on the mechanics of the amplified values, M<T>.  Each amplified type will need a distinct definition of Bind.

In addition to Bind, define a function which takes an unamplified value and amplifies it.  Call this function "Unit".

public static M<T> Unit<T>(this T value)

Together the amplified type, M<T>, the function Bind, and the function Unit enable function composition with amplified values.

Meet the Monads

Viola, we have invented monads.

Monads are a triple consisting of a type, a Unit function, and a Bind function.  Furthermore, to be a monad, the triple must satisfy three laws:

1.  Left Identity

     Bind(Unit(e), k) = k(e)

2.  Right Identity

     Bind(m, Unit) = m

3.  Associative

     Bind(m, x => Bind(k(x), y => h(y)) = Bind(Bind(m, x => k(x)), y => h(y))

The laws are similar to those of function composition.  This is not a coincidence.  They guarantee that the monad is well behaved and composition works properly.

To define a particular monad, the writer supplies the triple, thereby specifying the mechanics of the amplified values.

The Identity Monad

The simplest monad is the Identity monad.  The type represents a wrapper containing a value.

class Identity<T>
{
    public T Value { get; private set; }
    public Identity(T value) { this.Value = value; }
}

The Unit function takes a value and returns a new instance of Identity, which wraps the value.

static Identity<T> Unit<T>(T value)
{
    return new Identity<T>(value);
}

The bind function takes an instance of Identity, unwraps the value, and invokes the delegate, k, with the unwrapped value.  The result is a new instance of Identity.

static Identity<U> Bind<T,U>(Identity<T> id, Func<T,Identity<U>> k)
{
    return k(id.Value);
}

Consider a simple program that creates two Identity wrappers and performs an operation on the wrapped values.  First, bind x to the value within the wrapper containing the value five.  Then, bind y to the value within the wrapper containing the value six.  Finally, add the values, x and y, together.  The result is an instance of Identity wrapping the value eleven.

var r = Bind(Unit(5), x =>

            Bind(Unit(6), y =>

                Unit(x + y)));

Console.WriteLine(r.Value);

While this works, it is rather clumsy.  It would be nice to have syntax for dealing with the monad.  Fortunately, we do.

C# 3.0 introduced query comprehensions which are actually monad comprehensions in disguise.  We can rewrite the identity monad to use LINQ.  Perhaps, it should have been called LINM (Language INtegrated Monads), but it just doesn’t have the same ring to it.

Rename the method Unit to ToIdentity and Bind to SelectMany.  Then, make them both extension methods.

public static Identity<T> ToIdentity<T>(this T value)
{
    return new Identity<T>(value);
}

public static Identity<U> SelectMany<T, U>(this Identity<T> id, Func<T, Identity<U>> k)
{
    return k(id.Value);
}

The changes impact the calling code.

var r = 5.ToIdentity().SelectMany(
            x => 6.ToIdentity().SelectMany(
                y => (x + y).ToIdentity()));

Console.WriteLine(r.Value);

Equivalent methods are part of the standard query operators defined for LINQ.  However, the standard query operators also include a slightly different version of SelectMany for performance reasons.  It combines Bind with Unit, so that lambdas are not deeply nested.  The signature is the same except for an extra argument that is a delegate which takes two arguments and returns a value.  The delegate combines the two values together.  This version of SelectMany binds x to the wrapped value, applies k to x, binds the result to y, and then applies the combining function, s, to x and y.  The resultant value is wrapped and returned.

public static Identity<V> SelectMany<T, U, V>(this Identity<T> id, Func<T, Identity<U>> k, Func<T,U,V> s)
{
    return id.SelectMany(x => k(x).SelectMany(y => s(x, y).ToIdentity()));
}

Of course, we can remove some of the code from the generalized solution by using our knowledge of the Identity monad.

public static Identity<V> SelectMany<T, U, V>(this Identity<T> id, Func<T, Identity<U>> k, Func<T,U,V> s)
{
    return s(id.Value, k(id.Value).Value).ToIdentity();
}

The call-site does not need to nest lambdas.

var r = 5.ToIdentity()
         .SelectMany(x => 6.ToIdentity(), (x, y) => x + y);

Console.WriteLine(r.Value);

With the new definition of SelectMany, programmers can use C#’s query comprehension syntax.  The from notation binds the introduced variable to the value wrapped by the expression on the right.  This allows subsequent expressions to use the wrapped values without directly calling SelectMany.

var r = from x in 5.ToIdentity()
        from y in 6.ToIdentity()
        select x + y;

Since the original SelectMany definition corresponds directly to the monadic Bind function and because the existence of a generalized transformation has been demonstrated, the remainder of the post will use the original signature.  But, keep in mind that the second definition is the one used by the query syntax.

The Maybe Monad

The Identity monad is an example of a monadic container type where the Identity monad wrapped a value.  If we change the definition to contain either a value or a missing value then we have the Maybe monad.

Again, we need a type definition.  The Maybe type is similar to the Identity type but adds a property denoting whether a value is missing.  It also has a predefined instance, Nothing, representing all instances lacking a value.

class Maybe<T>
{
    public readonly static Maybe<T> Nothing = new Maybe<T>();
    public T Value { get; private set; }
    public bool HasValue { get; private set; }
    Maybe()
    {
        HasValue = false;
    }
    public Maybe(T value)
    {
        Value = value;
        HasValue = true;
    }
}

The Unit function takes a value and constructs a Maybe instance, which wraps the value.

public static Maybe<T> ToMaybe<T>(this T value)
{
    return new Maybe<T>(value);
}

The Bind function takes a Maybe instance and if there is a value then it applies the delegate to the contained value.  Otherwise, it returns Nothing.

public static Maybe<U> SelectMany<T, U>(this Maybe<T> m, Func<T, Maybe<U>> k)
{
    if (!m.HasValue)
        return Maybe<U>.Nothing;
    return k(m.Value);
}

The programmer can use the comprehension syntax to work with the Maybe monad.  For example, create an instance of Maybe containing the value five and add it to Nothing.

var r = from x in 5.ToMaybe()
        from y in Maybe<int>.Nothing
        select x + y;

Console.WriteLine(r.HasValue ? r.Value.ToString() : "Nothing");

The result is "Nothing".  We have implemented the null propagation of nullables without explicit language support.

The List Monad

Another important container type is the list type.  In fact, the list monad is at the heart of LINQ.  The type IEnumerable<T> denotes a lazily computed list.

The Unit function takes a value and returns a list, which contains only that value.

public static IEnumerable<T> ToList<T>(this T value)
{
    yield return value;
}

The Bind function takes an IEnumerable<T>, a delegate, which takes a T and returns an IEnumerable<U>, and returns an IEnumerable<U>.

public static IEnumerable<U> SelectMany<T, U>(this IEnumerable<T> m, Func<T, IEnumerable<U>> k)
{
    foreach (var x in m)
        foreach (var y in k(x))
            yield return y;
}

Now, the programmer can write the familiar query expressions with IEnumerable<T>.

var r = from x in new[] { 0, 1, 2 }
        from y in new[] { 0, 1, 2 }
        select x + y;

foreach (var i in r)
    Console.WriteLine(i);

Remember that it is the monad that enables the magic.

The Continuation Monad

The continuation monad answers the question that was posed at the end of the last post: how can a programmer write CPS code in a more palatable way?

The type of the continuation monad, K, is a delegate which when given a continuation, which takes an argument and returns an answer, will return an answer.

delegate Answer K<T,Answer>(Func<T,Answer> k);

The type K fundamentally differs from types Identity<T>, Maybe<T>, and IEnumerable<T>.  All the other monads represent container types and allow computations to be specified in terms of the values rather than the containers, but the continuation monad contains nothing.  Rather, it composes together continuations the user writes.

To be a monad, there must be a Unit function which takes a T and returns a K<T,Answer> for some answer type.

public static K<T, Answer> ToContinuation<T, Answer>(this T value)

What should it do?  When in doubt, look to the types.   The method takes a T and returns a function, which takes a function from T to Answer, and returns an Answer.  Therefore, the method must return a function and the only argument of that function must be a function from T to Answer.  Call the argument c.

return (Func<T, Answer> c) => ...

The body of the lambda must return a value of type Answer.  Values of type Func<T,Answer> and a T are available.  Apply c to value and the result is of type Answer.

return (Func<T, Answer> c) => c(value);

To be a monad, Bind must take a K<T,Answer> and a function from T to K<U, Answer> and return a K<U, Answer>.

public static K<U, Answer> SelectMany<T, U, Answer>(this K<T, Answer> m, Func<T, K<U, Answer>> k)

But what about the body?  The result must be of type K<U, Answer>, but how is a result of the correct type formed?

Expand K‘s definition to gain some insight.

return type

     Func<Func<U, Answer>, Answer>

m‘s type

     Func<Func<T, Answer>, Answer>

k‘s type

     Func<T, Func<Func<U, Answer>, Answer>>

Applying k to a value of type T results in a value of type K<U,Answer>, but no value of type T is available.  Build the return type directly by constructing a function, which takes a function from U to Answer.  Call the parameter c.

return (Func<U,Answer> c) => ...

The body must be type of Answer so that the return type of Bind is K<U,Answer>.  Perhaps, m could be applied to a function from T to Answer.  The result is a value of type Answer.

return (Func<U,Answer> c) => m(...)

The expression inside the invocation of m must be of type Func<T,Answer>.  Since there is nothing of that type, construct the function by creating a lambda with one parameter, x, of type T.

return (Func<U,Answer> c) => m((T x) => ...)

The body of this lambda must be of type Answer.  Values of type T, Func<U,Answer>, and Func<T,Func<Func<U,Answer>, Answer>> haven’t been used yet.  Apply k to x.

return (Func<U,Answer> c) => m((T x) => k(x)...)

The result is a value of type Func<Func<U,Answer>,Answer>.  Apply the result to c.

return (Func<U,Answer> c) => m((T x) => k(x)(c));

The continuation monad turns the computation inside out.  The comprehension syntax can be used to construct continuations.

Construct a computation, which invokes a continuation with the value seven.  Pass this computation to another computation, which invokes a continuation with the value six.   Pass this computation to another computation, which invokes a continuation with the result of adding the results of the first two continuations together.  Finally, pass a continuation, which replaces "1"s with "a"s, to the result.

var r = from x in 7.ToContinuation<int,string>()
        from y in 6.ToContinuation<int,string>()
        select x + y;

Console.WriteLine(r(z => z.ToString().Replace('1', 'a'))); // displays a3

The continuation monad does the heavy-lifting of constructing the continuations.

Monadic Magic

Beautiful composition of amplified values requires monads.  The Identity, Maybe, and IEnumerable monads demonstrate the power of monads as container types.  The continuation monad, K, shows how monads can readily express complex computation.

Stay tuned for more with monads.  Until then, see what monads can do for you.

Comments (36)

  1. Barry Kelly says:

    Excellent stuff. Describing monads in a practical, pragmatic way using the fairly well-known primitives of an imperative language is definitely the way to go to teach the concept to experienced programmers, IMO. They can then almost involuntarily see the compositional advantages of the idea. When integrated into a language and its flow of values through expressions, like Haskell, it’s almost like being able to overload the ‘;’ operator.

  2. Thank you so much for posting this Wes. I was hoping you’d return to Functional programming and this is more than I could have hoped for. Looking forward to reading your next post.

  3. Cale Gibbard says:

    While particular monads can of course be interesting, the abstraction of calling something a monad is generally really only useful if you design things such that code can be written which is polymorphic across different monads.

    Without that, you just have a bunch of separate combinator libraries that happen to have similar looking APIs. Functional programmers have been writing combinator libraries for years, and they’re generally considered a great idea, but to stop there would miss the main point of saying that such and such combinator library is a monad in the first place.

    For a simple example of the sort of function which one can write to work in all monads, consider the Haskell function sequence :: (Monad m) => [m a] -> m [a], which takes a list of monadic computations, and produces a computation which runs each of those in turn, giving a list of the results.

    In Haskell:

    sequence [] = return []

    sequence (x:xs) = do v <- x; vs <- sequence xs; return (v:vs)

    It works in any monad whatsoever — and that’s the whole point of giving a name to the abstraction in the first place, so that things like sequence, and other control structures like it (mapM/forM, replicateM, filterM, foldM, the rest of the contents of the Control.Monad and Data.Traversable libraries, etc.) can be written once and shared across various monadic libraries.

  4. C. Rebert says:

    Personally, the best explanation of monads that I’ve ever seen is: http://programming.reddit.com/info/64th1/comments/c02u9mb

    I think the big hurdle in explaining monads is the terminology, particularly "return", which I’m glad to see people are now replacing with "unit". This is definitely much clearer to the imperative programmer. And don’t even try bringing up Haskell’s do-notation, it just muddles people’s understanding further.

  5. You left out one thing, though: callcc.  How can you define the

    continuation monad without defining callcc?  Well, I’ll help a buddy

    out and give it a shot:

    K<T, Answer> callcc(Func<Func<T, K<U, Answer>>, K<T, Answer>> u)

    {

       return (Func<T, Answer> c) => u((T x) => (Func<U, Answer>  _) => c(x))(c)

    }

    As far as I can tell, it looks right, but I haven’t written any C# in

    over a year, I don’t have a C# compiler available, and I’ve never used

    generics before, so there’s no telling for sure.

    But I’m sure of one thing: it looks like crap. All of those pointy

    brackets for type parameterization is a real eye sore, especially the

    ones for function types.  We can’t we at least write (T -> U) instead

    of Func<T, U>?

  6. Andrew Davey says:

    Hehe funny how just yesterday I realised that multiple ‘from’ clauses map to SelectMany and thus are Bind!

    Great post – I look forward to reading more on this topic soon.

  7. Andrew Davey says:

    Can you release a code sample of this please?

    I tried to write up your examples, but I get:

    error CS1936: Could not find an implementation of the query pattern for source type ‘Library.K<int,string>’.  ‘SelectMany’ not found.

    Do I need to implement IQueryable<K<T, Answer>> and IQueryProvider somewhere? I’ve not made a custom LINQ implementation before so I’m a little lost!

    Thanks.

  8. Jon Skeet says:

    Andrew: Chances are you’re just missing a using directive:

    using System.Linq;

    SelectMany is an extension method on IEnumerable<T>, in System.Linq.Enumerable. If Library.K implements IEnumerable<T> somewhere, that should be okay.

    Mind you, I haven’t tried the code yet. I’m trying to get my head round the whole monad business, suspecting that I may well have implemented one somewhere when doing "push" LINQ…

    Jon

  9. Andrew Davey says:

    I already had the System.Linq include.

    The problem is the code is missing a version of SelectMany that takes an additional parameter I think.

    Looking in System.Linq.Enumerable I see a version of SelectMany with 3 parameters. I can’t get the type signature right yet though – needs some heavy thinking…

  10. Craig Stuntz says:

    Wes,

    How about LIMN (Language Integrated MoNads)?

    ("Limn" means "to trace the outline of." It’s a real word, though not a common one outside of Michiko Kakutani book reviews.)

    -Craig

  11. Cello! You’ve used an instrument as an exclamation!

  12. wesdyer says:

    Cale:

    Good point.  The C# type system is not powerful enough to create a generalized abstraction for monads which was the primary motivator for creating extension methods and the "query pattern"; however, the abstraction is still important in the minds of the monad writer because it formalizes a notion that is generally useful.  In future posts, I will show some very useful monads.

    C. Rebert:

    Actually, people haven’t started calling it "unit".  That is what it was originally called.  Haskell renamed unit to return and bind to >>=, which makes sense in their language.

    Peter:

    You are absolutely right.  You don’t need some of the angle brackets and you are missing some other ones ;).  My examples unnecessarily, explicitly type the lambdas for clarity.  You could have written:

           public static K<T, Answer> CallCC<T, U, Answer>(this Func<Func<T, K<U, Answer>>, K<T, Answer>> u)

           {

               return c => u(x => z => c(x))(c);

           }

    Andrew:

    You are not missing a reference to System.Linq, in fact you don’t need one.  You discovered the problem, you implemented the SelectMany with 2 parameters but not with 3 parameters.  Earlier in the post, I showed a generalized transformation from the 2 argument SelectMany to the 3 argument SelectMany.  Here is the solution for the continuation monad.

           public static K<V, Answer> SelectMany<T, U, V, Answer>(this K<T, Answer> m, Func<T, K<U, Answer>> k, Func<T, U, V> s)

           {

               return m.SelectMany(x => k(x).SelectMany(y => s(x, y).ToContinuation<V, Answer>()));

           }

    That should enable the query syntax.  Good luck and if you have any other problems then just ask.

    Craig:

    How about LIMO (Language Integrated MOnads)?

  13. Sadek Drobi says:

    That is exactly the post I’ve been waiting for!

    Yet Another Language Geek is one of my top 10 :)

    I have a feeling that Functional Programming is going to be the next geeky trend to replace patterns’ love.

    Monads forever! :)

  14. sdobrev says:

    This looks so much the same as the workflows in F#. Can’t wait to see how these stuffs get incorporated into Volta.

  15. Andrew Davey says:

    Thanks for the pointer. I managed to make some code working with WebRequest’s Begin/End async methods. (I’m not sure it’s the *best* way to achieve it.)

    I’m also thinking about reading a stream in a similar async manner.

    Is there a way to manage IDisposable resources inside the LINQ comprehension?

    In F# Workflows there is an explicit "use" method that ensures the disposable object is disposed at the right time.

    I’m looking eventually to get code like this:

    var page =

    from response in request.GetResponseAsync()

    let stream in response.GetResponseStream()

    from html in stream.ReadToEndAsync()

    select html

    I assume there are more posts coming our way… :)

  16. Andrew Davey says:

    Hello again, I put the (now improved) code online:

    http://www.aboutcode.net/2008/01/14/Async+WebRequest+Using+LINQ+Syntax.aspx

    if people want to see async web requests and stream reading in action.

  17. sdobrev says:

    I think it is now clear where the next CTP of Volta is going. The async attribute will be used not only for generating void Methods with last parameter the continuation, but also methods that return the continuation itself. This will be extremely useful in LINQ scenarios as the sample by Andrew. The C(#) will definitely sound more like F(#).

  18. Tanveer Badar says:

    Excellent post. It took me three re-readings and one week to fully understand what is present.

  19. Tom Kirby-Green says:

    Hi Wes. Just had to add another comment to say that along with your recent CPS article and now the Monad article you’ve given me some great stuff to try and wrap my so-called brain around. I’m torn between being super appreciative of the work you and the C# compiler folks do – and at the same time rather selfishly wishing you had more time to write blog posting like this one. Spoiled is what we are! :-)

  20. Emperor XLII says:

    I was recently inspired by a post on the monadic nature of Linq to dig out …

    http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=2586109&SiteID=1#2815902

  21. tom says:

    i visit your blog everyday hoping to find a new post it seems you are in a big project and couldnt give time to this blog. are you planning to write a new post? please do so

  22. Sadek Drobi says:

    Hi Wes,

    I’ve been trying to implement a Tree monad in C# and I went through several issues some of them seem to be annoying.

    First, I used a Binary Tree, i felt the Binary Tree suited better in monad. However, I defined the Unit to be the Leaf constructor. That works fine until I start to get several times amplified types! I didn’t find a method to reflatten the result to have a correct monad. Any suggestions?

    My second problem is that my binary tree monad SelectMany extension is not lazy evaluated. That means that for each select I do it exutes the whole recursion and yields a mapped tree.

    I didnt find an equivelant to yield for the tree (which would solve both problems), I tried to make my tree as each node has a value and a list of children and a leaf has only a value , so that i can get use of the yield keyword. But I couldn’t represent that as a monad (more precisely I couldn’t implement the SelectMany because I can not transform a node using the k transformer (knowing that a node has a value :S)

    Third, I really couldn’t understand which magic gets the compiler to know what is the value of k when using from and select keyword!

    It seems parsing the content of the monad and extracting the k from there. So if I have something like Tree<int> t= new Node<int>(new Leaf<int>(1),new Leaf<int>(2));

    It will strangely use this for the k function as the unit function.

    so if i do

    from v1 in t

    from v2 in t

    select v1+v2

    it will yield a very strange result. I really couldn’t understand where does the compiler get the unit and the k difinition from.

    Hope that my post is understandable.

    Sadek

  23. Thanks for the post.

    The transformation for the continuation monad really looks like the transformation for a element to its double dual, aka, I start from a value x, and I give back a function to evaluate function at that point x.

    I wonder what that mean in terms of category, functor, etc.

    Cheers,

    Nicolas Rolland

  24. sadek drobi says:

    Hi Wes,

    I tried to implement a lazy tree with a select on it, nothing is as easy as haskell :)

    what do you think of this? Am i missing something?

    public abstract class LazyTree<T>

       {

           private readonly Func<T> valueGetter;

           public LazyTree(Func<T> value)

           {

               this.valueGetter = value;

           }

           public T Value

           {

               get

               {

                   return valueGetter();

               }

           }

       }

       public class LazyNode<T> : LazyTree<T>

       {

           public LazyNode(Func<T> value, Func<IEnumerable<LazyTree<T>>> children)

               : base(value)

           {

               this.childrenGetter = children;

           }

           private readonly Func<IEnumerable<LazyTree<T>>> childrenGetter;

           public IEnumerable<LazyTree<T>> Children

           {

               get

               {

                   return this.childrenGetter();

               }

           }

       }

       public class LazyLeaf<T> : LazyTree<T>

       {

           public LazyLeaf(Func<T> value) : base(value) { }

       }

       public static class LazyTreeExtensions

       {

           public static LazyTree<R> Select<T, R>(this LazyTree<T> tree, Func<T, R> selector)

           {

               if (tree is LazyLeaf<T>)

                   return new LazyLeaf<R>(() => selector(tree.Value));

               else return new LazyNode<R>(() => selector(tree.Value),

                                          () => from t in (tree as LazyNode<T>).Children select Select(t, selector));

           }

  25. addys says:

    Ouch, my brain hurts.  I’ll need to come back to this post when I’m sober :)

  26. Dave says:

    Love your blog… I’ve learned so much from it. Do you plan on writing more blog posts sometime?

  27. Chaow says:

    I’m still waiting for your new post. Love your functional programming.

  28. Manoj Bhatty says:

    Great post! Really enjoyed reading it.

    A little formatting thing I noticed – the long lines of code (method declaration for example) don’t wrap around when reading it in iPhone and are completely cut off. No biggie unless you’ve a lot of iphone readers, but just to let you know.

  29. Raoul Duke says:

    bad css? if i make the font big, then the code examples get chopped off on the rhs. :-(

    otherwise, thanks for the post, it has been quite helpful in understanding monads!

  30. Strilanc says:

    Is linq implemented differently in VB?

    I can get the example to work in C#, but it won’t translate to VB. The error appears on the 1.ToIdentity line, complaining that it’s not an IEnumerable.

    C#:

    public static class TestClass {

       interface IFuture<T> { }

       public static IFuture<V> SelectMany<T, U, V>(this IFuture<T> id, Func<T, IFuture<U>> k, Func<T, U, V> s) {

           throw new NotSupportedException();

       }

       public static IFuture<T> ToIdentity<T>(this T value) {

           throw new NotSupportedException();

       }

       public static IFuture<int> test() {

           return from x in 1.ToIdentity()

                  from y in 2.ToIdentity()

                  select x + y;

       }

    }

    VB:

    Public Module TestModule

       Interface IFuture(Of T)

       End Interface

       <Runtime.CompilerServices.Extension()> Public Function SelectMany(Of T, U, V)(ByVal id As IFuture(Of T), ByVal k As Func(Of T, IFuture(Of U)), ByVal s As Func(Of T, U, V)) As IFuture(Of V)

           Throw New NotSupportedException()

       End Function

       <Runtime.CompilerServices.Extension()> Public Function ToIdentity(Of T)(ByVal value As T) As IFuture(Of T)

           Throw New NotSupportedException()

       End Function

       Public Function test() As IFuture(Of Integer)

           Return From x In 1.ToIdentity()

                  From y In 2.ToIdentity()

                  Select x + y

       End Function

    End Module

  31. Jason says:

    Wes,

    I think your CallCC implementation has a typo; you’re not using ‘z’ in the implementation.. And in order to do so, the function signature needs a small change:

    public static K<T, TAnswer> CallCC<T, U, TAnswer>(this Func<Func<U, K<U, TAnswer>>, K<T, TAnswer>> u)

    {

       return (Func<T, TAnswer> c) => u((U x) => (Func<U, TAnswer> z) => z(x))(c);

    }

  32. Jay says:

    I get LINQ and have seen (but not used) Haskell and F#. I’m a C/C++/C# man.

    What I found interesting was how you used multiple ‘from’ clauses, which was neat.

    What I don’t understand was the "6 + 7 to  a3" example. I get that this is a simple demonstration to show that the above discussion worked, but with this example I didn’t get a sense of what was actually gained.

    So can you or another commentator explain what is enabled by using the monad and continuation there? Is it just that you can use LINQ on a literal? (e.g. I couldn’t say "from i in 6 from j in 7 select i + j", but I can with this mumbo-jumbo? Why did you have to put "string" in there and why change the 1 to ‘a’?)

  33. Jay says:

    Responding to my own last comment, I found the article someone else linked (http://www.reddit.com/r/programming/comments/64th1/monads_in_python_in_production_code_you_can_and/c02u9mb) very useful to put this post of yours in context.

    I interpreted that article as saying that Bind is like a pipeline, passing along a tuple of information one if which is the primary data (like 6 and 7) and some "additional data" (like a possible Nothing state or string). And I’m starting to understand why the command-line piple used in PowerShell was codenamed Monad originally…

    So going with that interpretation, the 6 & 7 example uses ‘<int,string>’ because the int is for the primary numbers, and the string is the "additional data" you wanted carried along with your integer numbers.

    Then your LINQ query "from x in 6… from y in 7… select x + y" is returning something that can accept a lambda (the "z =>" part of the Console output line). That lambda will be run on… something. Clearly it gets a 1 and converts it to a, but I’m not sure where/when.

    So I’m going to map this to the Haskell. Given your description of ToContinuation as Unit and SelectMany as Bind… this makes:

       from x in 6.Unit

       from y in 7.Unit

       select x + y

    Something like the following Haskell

       unit 6 >>= ???

    …I don’t really understand the pipeline.

    All right, so what is K? K is the lambda you passed in, it takes an int and returns a string. So that’s the z.ToString() part of things and the "a" is just to prove it’s actually doing something.

    And what is "x + y"? Is this the g(x) in "f x >>= g >>= h"? Where did the operator + get overloaded?

    All right, this brings me back to the start of your monad talk:

    var r = Bind(Unit(5), x =>

               Bind(Unit(6), y =>

                   Unit(x + y)));

    This is what I presume maps to the LINQ style:

    var r = from x in 5.Unit

                 from y in 6.Unit

                 select x + y;

    And maybe (I don’t really believe):

    r =  unit 5 >>= unit 6 >>= x + y

    In all cases, I then have a supposedly handy function r() which I can use to show the number 11.

    Well clearly I’m over my head, but what’s the practical benefit of this? I can see that it is a nifty mapping that leverages C# syntax for some functional-style programming (F# would be better). But is there some case where the power of this would be evident? What do i do with this function?

    In other words, the thing still not clear to me is why it is helpful to say:

      Console.WriteLine(r(z => z.ToString().Replace(‘1’, ‘a’))); // displays a3

    vs something like this (sic):

      Console.WriteLine(r().ToString().Replace(‘1’, ‘a’)); // displays a3

    What did I gain with the extra indirection?

  34. nobody says:

    А что за албанский использовался в написании примеров?

  35. bradrhod says:

    When i got to the portion on making ToIdentity and SelectMany extension methods I expected the following code to compile.  I cannot seem to get the compiler to consider ToIdentity/SelectMany as extension to integer.  

    What am I mising?

    —-

    using System;

    using System.Collections.Generic;

    using System.Linq;

    using System.Text;

    namespace MonadFunctions

    {

       // the Identity Class

       class Identity<T>

       {

           public T Value { get; private set; }

           public Identity(T value) { this.Value = value; }

       }

       class Program

       {

           // the unit function

           public static Identity<T> ToIdentity<T>(this T value)

           {

               return new Identity<T>(value);

           }

           // the Bind function

           public static Identity<U> SelectMany<T, U>(this Identity<T> id, Func<T, Identity<U>> k)

           {

               return k(id.Value);

           }

           static void Main(string[] args)

           {

               var r = 5.ToIdentity().SelectMany(x => 6.ToIdentity().SelectMany(y => (x + y).ToIdentity()));

               Console.WriteLine(r.Value);

               Console.WriteLine(r.GetType());

           }

       }

    }