Udostępnij za pośrednictwem

The Marvels of Monads

  • Artykuł

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 theory.  Moggi 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 theunwrapped 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 areavailable.  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

  • Anonymous
    January 10, 2008
    PingBack from http://geeklectures.info/2008/01/10/the-marvels-of-monads/

  • Anonymous
    January 10, 2008
    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.

  • Anonymous
    January 10, 2008
    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.

  • Anonymous
    January 10, 2008
    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.

  • Anonymous
    January 10, 2008
    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.

  • Anonymous
    January 10, 2008
    The comment has been removed

  • Anonymous
    January 10, 2008
    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.

  • Anonymous
    January 10, 2008
    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.

  • Anonymous
    January 11, 2008
    The comment has been removed

  • Anonymous
    January 11, 2008
    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...

  • Anonymous
    January 11, 2008
    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

  • Anonymous
    January 11, 2008
    Cello! You've used an instrument as an exclamation!

  • Anonymous
    January 11, 2008
    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)?

  • Anonymous
    January 12, 2008
    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! :)

  • Anonymous
    January 13, 2008
    This looks so much the same as the workflows in F#. Can't wait to see how these stuffs get incorporated into Volta.

  • Anonymous
    January 13, 2008
    The comment has been removed

  • Anonymous
    January 14, 2008
    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.

  • Anonymous
    January 14, 2008
    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(#).

  • Anonymous
    January 16, 2008
    Excellent post. It took me three re-readings and one week to fully understand what is present.

  • Anonymous
    January 17, 2008
    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! :-)

  • Anonymous
    February 08, 2008
    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

  • Anonymous
    February 11, 2008
    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

  • Anonymous
    February 27, 2008
    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

  • Anonymous
    March 08, 2008
    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

  • Anonymous
    March 30, 2008
    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));        }

  • Anonymous
    July 09, 2008
    Ouch, my brain hurts.  I'll need to come back to this post when I'm sober :)

  • Anonymous
    September 03, 2008
    Love your blog... I've learned so much from it. Do you plan on writing more blog posts sometime?

  • Anonymous
    November 11, 2008
    I'm still waiting for your new post. Love your functional programming.

  • Anonymous
    April 09, 2009
    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.

  • Anonymous
    May 12, 2009
    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!

  • Anonymous
    June 25, 2009
    The comment has been removed

  • Anonymous
    July 30, 2009
    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); }

  • Anonymous
    September 13, 2009
    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'?)

  • Anonymous
    September 13, 2009
    The comment has been removed

  • Anonymous
    November 30, 2009
    А что за албанский использовался в написании примеров?

  • Anonymous
    May 13, 2010
    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());        }    } }