Monads in C#: Which Part Is The Monad?

In my previous post on refactoring some code, several people responded in the comments and via twitter that I should look at the Maybe<T> monad as an option. Now, I have to be honest… the potty-humor-teenager in me wants to giggle a little every time I hear, read, or say “monad”… but I’m sure that’s old news at this point. I’ve heard a lot about these things and I’ve never really had a reason to understand them until now. At least, that’s what I thought… but once I started reading about them and how they can be applied in C#, I realized that I’ve probably been using them for a long time and didn’t know it. In fact, LINQ is pretty much a DSL around monads… granted, I’ve never used the LINQ DSL, but I use the extension methods that come with LINQ pretty regularly.

Given all that, I’ve been doing some r&d to learn how to implement my own monadic method chaining goodness, and I’ve come to a point where I’m not actually sure which parts of the code are the monads and which parts are implementation details that are side effects of doing this in C#. I’m hoping you, dear reader, can help me understand this. I’m writing this blog post as a learning tool for myself – not only to ask questions, but also to see what I can learn by solidifying my knowledge into a concrete form: this blog post.

 

Implementing Maybe<T>

Based on several articles and blog posts that I’ve read, I decided to implement the canonical Maybe<T> example. This made sense because that’s what people suggested I look at, and it also seems to be a very popular example. What I came up with is the following Maybe<T> class:

   1: public sealed class Maybe<T>

   2: {

   3:     public static Maybe<T> None = new Maybe<T>(default(T));

   4:  

   5:     private T value;

   6:     public T Value

   7:     {

   8:         get

   9:         {

  10:             return value;

  11:         }

  12:         set { this.value = value; }

  13:     }

  14:  

  15:     public bool HasValue

  16:     {

  17:         get

  18:         {

  19:             bool hasValue = false;

  20:             if (Value != null && !Value.Equals(default(T)))

  21:                 hasValue = true;

  22:             return hasValue;

  23:         }

  24:     }

  25:  

  26:     public Maybe(T value)

  27:     {

  28:         Value = value;

  29:     }

  30: }

This allows me to check whether I have a value or not, and get that value when I want to. (Note that I did not use the built in Nullable<T> from .NET because that class has a “where T: struct” clause on the generics type so I would not be able to use it on a Class type).

Next, I implemented several extension methods that I found via this article by Dmitri Nesteruk.

   1: public static class MaybeExtensions

   2: {

   3:     public static Maybe<T> ToMaybe<T>(this T input)

   4:     {

   5:         return new Maybe<T>(input);

   6:     }

   7:  

   8:     public static Maybe<TResult> Get<TInput, TResult>(this Maybe<TInput> maybe, Func<TInput, TResult> func)

   9:     {

  10:         Maybe<TResult> result;

  11:         if (maybe.HasValue)

  12:             result = new Maybe<TResult>(func(maybe.Value));

  13:         else

  14:             result = Maybe<TResult>.None;

  15:         return result;

  16:     }

  17:  

  18:     public static Maybe<TInput> If<TInput>(this Maybe<TInput> maybe, Func<TInput, bool> func)

  19:     {

  20:         Maybe<TInput> result;

  21:         if (maybe.HasValue && func(maybe.Value))

  22:             result = maybe;

  23:         else

  24:             result = Maybe<TInput>.None;

  25:         return result;

  26:     }

  27:     

  28:     public static TResult Return<TInput, TResult>(this Maybe<TInput> maybe, Func<TInput, TResult> func, TResult defaultValue)

  29:     {

  30:         TResult result = defaultValue;

  31:         if (maybe.HasValue)

  32:             result = func(maybe.Value);

  33:         return result;

  34:     }

  35: }

And lastly, I put together a sample that uses these methods:

   1: var foo = new Foo();

   2:  

   3: var output = foo.ToMaybe()

   4:     .Get(SomeMethodToRetrieveABar)

   5:     .If(CheckSomethingComplexWithBarHere)

   6:     .Get(r => r.Baz)

   7:     .Return(z => z.Name, "nothing here. move along");

   8:  

   9: Console.WriteLine(output);

In this example, if any of the method calls or funcs returns a null, I will end up with “nothing here. move along” as the text written to my console. However, if none of them produces a null value, then I will end up retrieving the Baz.Name property from my object graph (which looks like: Foo, Foo.Bar, Bar.Baz, Baz.Name).

 

A Long, Confusing Definition Of Monad

Now that I have this in place, I find myself asking… which part of this is the actual monad? According to Wikipedia, a monad:

is a kind of abstract data type constructor used to represent computations (instead of data in the domain model). Monads allow the programmer to chain actions together to build a pipeline, in which each action is decorated with additional processing rules provided by the monad. Programs written in functional style can make use of monads to structure procedures that include sequenced operations, or to define arbitrary control flows (like handling concurrency, continuations, or exceptions).

Formally, a monad is constructed by defining two operations (bind and return) and a type constructor M that must fulfill several properties to allow the correct composition of monadic functions (i.e. functions that use values from the monad as their arguments). The return operation takes a value from a plain type and puts it into a monadic container of type M. The bind operation performs the reverse process, extracting the original value from the container and passing it to the associated next function in the pipeline.

A programmer will compose monadic functions to define a data-processing pipeline. The monad acts as a framework, as it’s a reusable behavior that decides the order in which the specific monadic functions in the pipeline are called, and manages all the undercover work required by the computation. The bind and return operators interleaved in the pipeline will be executed after each monadic function returns control, and will take care of the particular aspects handled by the monad.

When I first read this, I got lost… very lost. So I started reading other articles by other developers. However, it wasn’t until I had actually implemented the Maybe<T> and a few other examples of what I think are monadic functions, that I started to understand what this text and those other articles are talking about. But I’m still not completely sure, here… so I want to pick out a few key parts of the above text and use them to analyze the code I wrote, hopefully identifying the actual monads in my sample code.

 

Return And Bind

When I first started reading the Maybe<T> examples, I thought it was the Maybe<T> class itself that was the monad. After all, the second paragraph in the above text talks about putting values into a container and extracting them, calling this Return and Bind, respectfully. In the case of Maybe<T>, that seems fairly obvious: I’m putting a value into the Maybe<T> class through the constructor, which should be the Return part, and then I’m extracting the value through the .Value property, which should be the Bind part. The problem I ran into is that the Dmitri Nesteruk article I linked to (where I got the extension methods) does not use a Maybe<T> class. This article uses the extension methods entirely, and yet it claims to be monads. I assume Dmitri knows what he is talking about and therefore my assumption of Maybe<T> being the monad is incorrect.

 

Monadic Functions

The third paragraph in the above text begins to give me a better picture, I think. “A programmer will compose monadic functions to define a data-processing pipeline.” Aha! Perhaps it is the actual extension methods that are the monads? Or at least, these are the monadic function that this paragraph refers to. But I don’t think that the extension methods are themselves the monad because the paragraph goes on to talk about the monad being a framework in which monadic functions are chained together. It also says the monad itself manages the order of execution. So then the monad isn’t the individual methods.

 

Are Monads In C# A Concept More Than A Construct?

I’m starting to get the feeling that a monad implemented in C# is more of a concept or aggregation of ideas and implementation detail, than an explicit construct. Given everything that the wikipedia article says, given all the examples I’ve looked at, and given the example that I show above, I think the actual monad is the aggregation of the extension methods, the Maybe<T> and calling them in the specific order that I have laid out in my code. Therefore, this sample code is the actual monad:

   1: var output = foo.ToMaybe()

   2:     .Get(SomeMethodToRetrieveABar)

   3:     .If(CheckSomethingComplexWithBarHere)

   4:     .Get(r => r.Baz)

   5:     .Return(z => z.Name, "nothing here. move along");

This code represents is the pipeline of monadic functions, put together in the specific order that they will be called, using the monadic extension methods that I created around the Maybe<T> type. Therefore, the concept of a monad is represented in this implementation detail.

 

Return And Bind, Again

If a monad in C# is more of a concept – more like a design pattern where the intention is critical in determining which specific pattern was used – then this would also reconcile my questioning of Dmitri’s article. It’s not the individual methods that are the monad – it’s the pipelined execution and examples that he gives that are the actual monad. In his article, for example, he shows this code:

   1: string postCode = this.With(x => person)

   2:     .If(x => HasMedicalRecord(x))]

   3:     .With(x => x.Address)

   4:     .Do(x => CheckAddress(x))

   5:     .With(x => x.PostCode)

   6:     .Return(x => x.ToString(), "UNKNOWN");

This is the monad, itself, just like my code right above it is the monad. In Dmitri’s example and methods, he is not using a generics class to Return and Bind as my example does. Rather, he is allowing the language to implicitly Return and Bind.

When the With method is called in Dmitri’s code, this is implicitly the first Return of the monad; not because the With method itself is the Return, but because this is the first part of the monad and the value is being wrapped into a type that the monadic functions can understand. It just happens to be, in this case, that the monadic functions can take any type through the use of generics in C#. In my example code, the .ToMaybe() method is the explicit Return portion of the monad. I am explicitly wrapping the value in a type that my monadic extension methods can use.

(Note: don’t confuse the “Return” method at the end of the pipeline with the “Return” concept of a monad. They aren’t the same. The Return method is just a poorly named method in this case, because it muddies the waters and makes it seem like this is the Return concept in the monad.)

The Bind occurs every time a monadic function is called. In Dmitri’s code, Bind is again implicit. Because the generics type system in C# allows us to pass any type we want, we don’t have to explicitly Bind the value to the method calls. We can simply pass them along. In my example code, though, I am explicitly doing the Bind when I retrieve the .Value and pass it into the func delegate: func(maybe.Value). This is the Bind portion.

After the Bind occurs, we once again Return the wrapped value. Again, Dmitri’s code does this implicitly with generics and I do it explicitly with my Maybe<T> class.

 

Will The Real Monad Please Stand Up?

How am I doing, here? How close am I? How far off? What detail am I missing? I’m still trying to get my head completely wrapped around all of this and I really want to some additional expert opinion weighed in on this. Please, please PLEASE let me know where I’ve gone wrong and what I need to do to correct my understanding! Everything I’ve said so far seems to make sense to me, so far. I hope it makes sense to the experts and to the people that are trying to learn this stuff, too.

 

Resources On Monads In .NET

Here’s the articles and blog posts that I’ve looked at, so far, that have helped me in my journey. Hopefully this will help others, as well.

If anyone else has other great resources and links on Monads in .NET (especially monads in C#), please post them in the comments here or in your own blog with a link back to this post.


Post Footer automatically generated by Add Post Footer Plugin for wordpress.

About Derick Bailey

Derick Bailey is an entrepreneur, problem solver (and creator? :P ), software developer, screecaster, writer, blogger, speaker and technology leader in central Texas (north of Austin). He runs SignalLeaf.com - the amazingly awesome podcast audio hosting service that everyone should be using, and WatchMeCode.net where he throws down the JavaScript gauntlets to get you up to speed. He has been a professional software developer since the late 90's, and has been writing code since the late 80's. Find me on twitter: @derickbailey, @mutedsolutions, @backbonejsclass Find me on the web: SignalLeaf, WatchMeCode, Kendo UI blog, MarionetteJS, My Github profile, On Google+.
This entry was posted in .NET, C#, Monads, Principles and Patterns. Bookmark the permalink. Follow any comments here with the RSS feed for this post.
  • http://fernandozamorajimenez.blogspot.com Fernando Zamora

    Wow.I am really trying to understand this material it
    s like whew… right over my head. It almost seems that you may be confusing concepts from the fluent interface with monad concept. But then again you know more than I do about monads. Just my two cents worth.

  • http://www.lostechies.com/members/derick.bailey/default.aspx derick.bailey

    @Fernando – yeah, i was thinking about the whole fluent interface thing as i was writing this. i don’t think i’m confusing the two at all… i think they are very closely related. they go hand in hand. many fluent interface implementations are likely going to be monads. … at least, i think so. we’ll see if someone else can validate that. :)

  • http://realfiction.net Frank Quednau

    When you move on in the very same wikipedia article (Concepts/Definition), I think it all becomes a lot clearer. A monad is defined by …
    - “A type construction that defines, for every underlying type, how to obtain a corresponding monadic type.” : The mere ability to say that for every T you can construct a Maybe should satisfy this condition.
    - “A unit function that maps a value in an underlying type to a value in the corresponding monadic type.” : This is quite clearly your extension method “ToMaybe()”
    - “A binding operation of polymorphic type (M t)→(t→M u)→(M u)”: Looks weird, but check out the signature of your e.g. “If”:
    Maybe If(this Maybe maybe, Func func)
    Input is a type of your “nested” monadic type system. Then comes a mapping from a non-monadic type to a monadic one. This doesn’t become apparent in the function signature, but you will notice that the “Func” is used to construct an instance in the monadic type system. Finally the result is an instance of the Monadic type system. Hence, your “If” is the “bind” part of the monad. In this case “t” = “u”, but in your “Get”, “t” and “u” can be different types.

    Chaining comes automatically, since the output of a bind is part of the Monadic type system and you have ensured that for every type “t” or “u” (sticking to the above definition) there is a mapping to the monadic type system.

    As another example LINQ is “almost” monadic. What it has missing is a unit function from T -> IEnumerable which you can provide easy enough:
    public IEnumerable
    ToEnumerable(this T obj) { return new T[] { obj }; }

    You’ll probably recognize that e.g. the “Select” has a very similar structure, with the monadic type system being IEnumerable . Again, method chaining follows from the mere definition of a monad. It looks similar to a fluent interface but I wouldn’t confuse the two, as it doesn’t help and in fluent interfaces you often just return the instance on which you called the method, sparing you the use of “;”

    That’s my 2 cents, almost a blog post in itself :)

  • Omer Mor
  • http://lorgonblog.spaces.live.com/blog/ Brian McNamara

    The first seven or so entries on my blog are about monadic parser combinators in C#.

    http://lorgonblog.spaces.live.com/?_c11_BlogPart_pagedir=Last&_c11_BlogPart_BlogPart=summary&_c=BlogPart

  • http://www.lostechies.com/members/derick.bailey/default.aspx derick.bailey

    @Frank – ah! ok… i think i was on the right path, but didn’t quite get some of those details correct, surrounding what the Bind actually is. Your explanation makes sense, though. I think I was in the right area, but not quite the right perspective on when it happens. Thanks for clarifying some of this for me. :)

    @Omar and @Brian – thanks for the links. i’ll definitely be reading them soon. :)

  • Pearce Shea

    I think that the only people that “get” Monads on the first approach are those who are fresh from a course or book on abstract algebra or people already steeped in functional programming languages.

    Frank’s post above, however, pretty succinctly describes what a Monad is.

    Another great resource for this and understanding how languages (in this case, more c++ than c#) are hung off of mathematical concepts and how both work, conceptually is McJones and Stepanov’s Elements of Programming (chapter 5 deals explicitly with monoids, not to be confused with monoids, rings etc). It’s a small book, and unless you are very mathematically inclined it will probably need a deliberate reading, but I’ve found it to be hugely helpful.

    And finally, it seems clear to me that most fluent interfaces would indeed be monads (or at least, that seems to be the simplest way to implement a fluent interface that I can think of).

  • http://murrayon.net/ Mike Murray

    Here is the promised follow-up post to my earlier one on the Maybe Monad that you referenced: http://murrayon.net/2010/09/maybe-monad-extensions.html

  • http://Http://khebbie.dk Klaus Hebsgaard

    Not that i have a lot of experience with the maybe type, but i have been following some discussions on the mailing list for “growing object oriented systems”
    One of the concepts of the maybe type that i find interesting and still am not comfortable with is the fact that some prefer to implement it as ie. An ienumerable. That way you could treat the result the same way no matter if its a null result or not…

  • http://derek-says.blogspot.com Derek Fowler

    Dmitri’s post inspired me to write a follow up too. My take on it was that the Maybe type removes the need for null checking in a function as it prevents the function from being called at all. Here’s my post:

    http://derek-says.blogspot.com/2010/09/null-object-pattern-and-maybe-monad.html

    @Frank How about… public IEnumerable ToEnumerable(this T obj) { yield return obj; }

  • mahmud khaled

    may be you would like this:
    http://blogs.msdn.com/b/wesdyer/archive/2008/01/11/the-marvels-of-monads.aspx

    PS. apologies if you already know about this.

  • http://executableintent.com/ Bryan Watts

    My metaphor for understanding monads is “amplified data”. A monad defines a higher level of abstraction at which we can reason about a certain type of object. A monad instance thus amplifies its data by raising it to that level.

    The intent behind a particular amplification defines the monad:

    Identity: data is not amplified

    Maybe: data may be absent

    IEnumerable: data has a cardinality of many

    In each of these, T is the amplified data and the generic type is the monad. They are identified by the level of abstraction to which they raise the target data type.

  • http://devtalk.net Dmitri

    I think the key here is the duality between null/non-null and Some/None or HasValue. And both approaches are equally fine, though using ‘null’ to indicate absence is probably better in terms of performance since no wrapper objects are created. That and the fact that wrapper objects typically have API issues such as having to get their Value, and so on.

    • Arthur

      Any comment on what part of this is a Monad? Personally don’t care about the performance of blog example code :P

  • Larry O’Brien

    I imagine you’ve worked this all out, but I would say that you were closest with “Maybe< T> is the monad.” In the object-oriented paradigm, it’s correct to speak of a monad as a parameterized type that implements the `bind` and `return` functions in a way that satisfies the “monad laws” (http://www.haskell.org/haskellwiki/Monad_Laws ) But of course monads are not limited to (or indeed, common in) OOP, so that’s why almost all discussions use the language of FP or mathematics. To an OOP programmer, these discussions are confusing, since they introduce lots of familiar-but-not-quite-the-same terms. Since the “monad part” is the semantics of the behavior, it seems a little wrong to me to call it a pattern — just as it would seem a little wrong to say that the `Map` interface is a pattern for its implementing `HashMap`. (As you’ve no-doubt discovered, monads and collection classes are the “secret sauce” that makes LINQ so powerful and general-purpose.)