In C#, What is a monad?

Question

There is a lot of talk about monads these days. I have read a few articles / blog posts, but I can't go far enough with their examples to fully grasp the concept. The reason is that monads are a functional language concept, and thus the examples are in languages I haven't worked with (since I haven't used a functional language in depth). I can't grasp the syntax deeply enough to follow the articles fully ... but I can tell there's something worth understanding there.

However, I know C# pretty well, including lambda expressions and other functional features. I know C# only has a subset of functional features, and so maybe monads can't be expressed in C#.

However, surely it is possible to convey the concept? At least I hope so. Maybe you can present a C# example as a foundation, and then describe what a C# developer would wish he could do from there but can't because the language lacks functional programming features. This would be fantastic, because it would convey the intent and benefits of monads. So here's my question: What is the best explanation you can give of monads to a C# 3 developer?

Thanks!

(EDIT: By the way, I know there are at least 3 "what is a monad" questions already on SO. However, I face the same problem with them ... so this question is needed imo, because of the C#-developer focus. Thanks.)

Solution 1

Most of what you do in programming all day is combining some functions together to build bigger functions from them. Usually you have not only functions in your toolbox but also other things like operators, variable assignments and the like, but generally your program combines together lots of "computations" to bigger computations that will be combined together further.

A monad is some way to do this "combining of computations".

Usually your most basic "operator" to combine two computations together is ;:

a; b

When you say this you mean "first do a, then do b". The result a; b is basically again a computation that can be combined together with more stuff. This is a simple monad, it is a way of combing small computations to bigger ones. The ; says "do the thing on the left, then do the thing on the right".

Another thing that can be seen as a monad in object oriented languages is the .. Often you find things like this:

a.b().c().d()

The . basically means "evaluate the computation on the left, and then call the method on the right on the result of that". It is another way to combine functions/computations together, a little more complicated than ;. And the concept of chaining things together with . is a monad, since it's a way of combining two computations together to a new computation.

Another fairly common monad, that has no special syntax, is this pattern:

rv = socket.bind(address, port);
if (rv == -1)
  return -1;

rv = socket.connect(...);
if (rv == -1)
  return -1;

rv = socket.send(...);
if (rv == -1)
  return -1;

A return value of -1 indicates failure, but there is no real way to abstract out this error checking, even if you have lots of API-calls that you need to combine in this fashion. This is basically just another monad that combines the function calls by the rule "if the function on the left returned -1, do return -1 ourselves, otherwise call the function on the right". If we had an operator >>= that did this thing we could simply write:

socket.bind(...) >>= socket.connect(...) >>= socket.send(...)

It would make things more readable and help to abstract out our special way of combining functions, so that we don't need to repeat ourselves over and over again.

And there are many more ways to combine functions/computations that are useful as a general pattern and can be abstracted in a monad, enabling the user of the monad to write much more concise and clear code, since all the book-keeping and management of the used functions is done in the monad.

For example the above >>= could be extended to "do the error checking and then call the right side on the socket that we got as input", so that we don't need to explicitly specify socket lots of times:

new socket() >>= bind(...) >>= connect(...) >>= send(...);

The formal definition is a bit more complicated since you have to worry about how to get the result of one function as an input to the next one, if that function needs that input and since you want to make sure that the functions you combine fit into the way you try to combine them in your monad. But the basic concept is just that you formalize different ways to combine functions together.

Solution 2

It has been a year since I posted this question. After posting it, I delved into Haskell for a couple of months. I enjoyed it tremendously, but I placed it aside just as I was ready to delve into Monads. I went back to work and focused on the technologies my project required.

And last night, I came and re-read these responses. Most importantly, I re-read the specific C# example in the text comments of the Brian Beckman video someone mentions above. It was so completely clear and illuminating that I’ve decided to post it directly here.

Because of this comment, not only do I feel like I understand exactly what Monads are … I realize I’ve actually written some things in C# that are Monads … or at least very close, and striving to solve the same problems.

So, here’s the comment – this is all a direct quote from the comment here by sylvan:

This is pretty cool. It's a bit abstract though. I can imagine people who don't know what monads are already get confused due to the lack of real examples.

So let me try to comply, and just to be really clear I'll do an example in C#, even though it will look ugly. I'll add the equivalent Haskell at the end and show you the cool Haskell syntactic sugar which is where, IMO, monads really start getting useful.

Okay, so one of the easiest Monads is called the "Maybe monad" in Haskell. In C# the Maybe type is called Nullable<T>. It's basically a tiny class that just encapsulates the concept of a value that is either valid and has a value, or is "null" and has no value.

A useful thing to stick inside a monad for combining values of this type is the notion of failure. I.e. we want to be able to look at multiple nullable values and return null as soon as any one of them is null. This could be useful if you, for example, look up lots of keys in a dictionary or something, and at the end you want to process all of the results and combine them somehow, but if any of the keys are not in the dictionary, you want to return null for the whole thing. It would be tedious to manually have to check each lookup for null and return, so we can hide this checking inside the bind operator (which is sort of the point of monads, we hide book-keeping in the bind operator which makes the code easier to use since we can forget about the details).

Here's the program that motivates the whole thing (I'll define the Bind later, this is just to show you why it's nice).

 class Program
    {
        static Nullable<int> f(){ return 4; }        
        static Nullable<int> g(){ return 7; }
        static Nullable<int> h(){ return 9; }


        static void Main(string[] args)
        {
            Nullable<int> z = 
                        f().Bind( fval => 
                            g().Bind( gval => 
                                h().Bind( hval =>
                                    new Nullable<int>( fval + gval + hval ))));

            Console.WriteLine(
                    "z = {0}", z.HasValue ? z.Value.ToString() : "null" );
            Console.WriteLine("Press any key to continue...");
            Console.ReadKey();
        }
    }

Now, ignore for a moment that there already is support for doing this for Nullable in C# (you can add nullable ints together and you get null if either is null). Let's pretend that there is no such feature, and it's just a user-defined class with no special magic. The point is that we can use the Bind function to bind a variable to the contents of our Nullable value and then pretend that there's nothing strange going on, and use them like normal ints and just add them together. We wrap the result in a nullable at the end, and that nullable will either be null (if any of f, g or h returns null) or it will be the result of summing f, g, and h together. (this is analogous of how we can bind a row in a database to a variable in LINQ, and do stuff with it, safe in the knowledge that the Bind operator will make sure that the variable will only ever be passed valid row values).

You can play with this and change any of f, g, and h to return null and you will see that the whole thing will return null.

So clearly the bind operator has to do this checking for us, and bail out returning null if it encounters a null value, and otherwise pass along the value inside the Nullable structure into the lambda.

Here's the Bind operator:

public static Nullable<B> Bind<A,B>( this Nullable<A> a, Func<A,Nullable<B>> f ) 
    where B : struct 
    where A : struct
{
    return a.HasValue ? f(a.Value) : null;
}

The types here are just like in the video. It takes an M a (Nullable<A> in C# syntax for this case), and a function from a to M b (Func<A, Nullable<B>> in C# syntax), and it returns an M b (Nullable<B>).

The code simply checks if the nullable contains a value and if so extracts it and passes it onto the function, else it just returns null. This means that the Bind operator will handle all the null-checking logic for us. If and only if the value that we call Bind on is non-null then that value will be "passed along" to the lambda function, else we bail out early and the whole expression is null. This allows the code that we write using the monad to be entirely free of this null-checking behaviour, we just use Bind and get a variable bound to the value inside the monadic value (fval, gval and hval in the example code) and we can use them safe in the knowledge that Bind will take care of checking them for null before passing them along.

There are other examples of things you can do with a monad. For example you can make the Bind operator take care of an input stream of characters, and use it to write parser combinators. Each parser combinator can then be completely oblivious to things like back-tracking, parser failures etc., and just combine smaller parsers together as if things would never go wrong, safe in the knowledge that a clever implementation of Bind sorts out all the logic behind the difficult bits. Then later on maybe someone adds logging to the monad, but the code using the monad doesn't change, because all the magic happens in the definition of the Bind operator, the rest of the code is unchanged.

Finally, here's the implementation of the same code in Haskell (-- begins a comment line).

-- Here's the data type, it's either nothing, or "Just" a value
-- this is in the standard library
data Maybe a = Nothing | Just a

-- The bind operator for Nothing
Nothing >>= f = Nothing
-- The bind operator for Just x
Just x >>= f = f x

-- the "unit", called "return"
return = Just

-- The sample code using the lambda syntax
-- that Brian showed
z = f >>= ( \fval ->
     g >>= ( \gval ->  
     h >>= ( \hval -> return (fval+gval+hval ) ) ) )

-- The following is exactly the same as the three lines above
z2 = do 
   fval <- f
   gval <- g
   hval <- h
   return (fval+gval+hval)

As you can see the nice do notation at the end makes it look like straight imperative code. And indeed this is by design. Monads can be used to encapsulate all the useful stuff in imperative programming (mutable state, IO etc.) and used using this nice imperative-like syntax, but behind the curtains, it's all just monads and a clever implementation of the bind operator! The cool thing is that you can implement your own monads by implementing >>= and return. And if you do so those monads will also be able to use the do notation, which means you can basically write your own little languages by just defining two functions!

Solution 3

A monad is essentially deferred processing. If you are trying to write code that has side effects (e.g. I/O) in a language that does not permit them, and only allows pure computation, one dodge is to say, "Ok, I know you won't do side effects for me, but can you please compute what would happen if you did?"

It's sort of cheating.

Now, that explanation will help you understand the big picture intent of monads, but the devil is in the details. How exactly do you compute the consequences? Sometimes, it isn't pretty.

The best way to give an overview of the how for someone used to imperative programming is to say that it puts you in a DSL wherein operations that look syntactically like what you are used to outside the monad are used instead to build a function that would do what you want if you could (for example) write to an output file. Almost (but not really) as if you were building code in a string to later be eval'd.

Solution 4

I'm sure other users will post in-depth, but I found Brian Beckman: Don't fear the Monad video helpful to an extent, but I will say that I'm still not to the point of fluency with the concept such that I could (or should) begin solving problems intuitively with Monads.

View more solutions

Comments

[Razzie]

Please note that it is actually a C# 3.0 developer. Don't mistake it with .NET 3.5. Other than that, nice question.

[Erik Forbes]

It's worth pointing out that LINQ query expressions are an example of monadic behavior in C# 3.

[josesuero]

I still think it's a duplicate question. One of the answers in stackoverflow.com/questions/2366/can-anyone-explain-monads link to channel9vip.orcsweb.com/shows/Going+Deep/…, where one of the comments has a very nice C# example. :)

[Salma b]

Read The Marvels of Monads. I think it's exactly what you're looking for.

[Charlie Flowers]

Still, that's just one link from one answer to one of the SO questions. I see value in a question focused on C# developers. It is something I would ask a functional programmer who used to do C# if I knew one, so it seems reasonable to ask it on SO. But I respect your right to your opinion as well.

[josesuero]

Isn't one answer all you need though? ;) My point is just that one of the other questions (and now this one as well, so yay) did have a C#-specific answer (which seems really well written, actually. Probably the best explanation I've seen)

[Johan]

possible duplicate of What is a monad?

[Bruno Brant]

No one looking at Monads from a C# background (or any OO background) should miss the excellent articles from Eric Lippert.

[Eric Lippert]

Thanks for the shout-out. :-) See also stackoverflow.com/questions/2704652/…

[Joel Coehoorn]

Can you elaborate? What is it about an interface that relates it to monads?

[OscarRyz]

Like in the I Robot book? Where the scientist ask a computer to calculate space travel and ask them to skip certain rules? : ) :) :) :)

[josesuero]

What I found even more helpful was the comment containing a C# example below the video.

[Jörg W Mittag]

Great answer! I'm going to throw in a quote by Oliver Steele, trying to relate Monads to operator overloading à la C++ or C#: Monads allow you to overload the ';' operator.

[TheMissingLINQ]

I dunno about more helpful, but it certainly put the ideas in practice.

[hao]

I think the blog post expends several paragraphs devoted to that question.

[ChaosPandion]

Personally I prefer F#'s version of the monad, but in either case they are awesome.

[Mike Hadlow]

Hmm, A Monad can be used for deferred processing and to encapsulate side effecting functions, indeed that was it's first real application in Haskell, but it actually a far more generic pattern. Other common uses include error handling and state management. The syntactic sugar (do in Haskell, Computation Expressions in F#, Linq syntax in C#) is merely that and fundamental to Monads as such.

[kappasims]

Thank you for coming back here and updating your post. It's follow-ups like these which help programmers who are looking into a specific area really understand how fellow programmers ultimately regard said area, instead of simply having "how do I do x in y technology" to go off of. You da man!

[Jimmy Hoffa]

@JörgWMittag I read that quote before, but it sounded like overly heady nonsense. Now that I do understand monads and read this explanation of how ';' is one, I get it. But I think it's really an irrational statement to most imperative developers. ';' isn't seen as an operator anymore than // is to most.

[Jimmy Hoffa]

I've taken the same path you have basically and arrived at the same place understanding monads, that said this is the single best explanation of a monad's binding behavior I have ever seen for an imperative developer. Though I think you're not quite touching on everything about monads which is a little more explained above by sth.

[Charlie Flowers]

@Jimmy Hoffa - no doubt you're right. I think to really understand them deeper, the best way is to start using them a lot and get experience. I haven't yet had that opportunity, but I hope to soon.

[liang]

It seems monad is just a higher level of abstraction in terms of programming, or it's just a continous and non-differentiable function definition in mathematics. Either way, they're not new concept, especially in mathematics.

[pyon]

@MikeHadlow: The monad instances for error handling (Maybe and Either e) and state management (State s, ST s) strike me as particular instances of "Please compute what would happen if you did [side effects for me]". Another example would be nondeterminism ([]).

[Luis]

Are you sure that you know what a monad is? Monads is not a "function" or computation, there are rules for monads.

[Will Ness]

this is exactly right; with one (well, two) additions that it is an E DSL, i.e. embedded DSL, as each "monadic" value is a valid value of your "pure" language itself, standing for a potentially impure "computation". Furthermore, a monadic "bind" construct exist in your pure language which allows you to chain pure constructors of such values where each will be invoked with the result from its preceding computation, when the whole combined computation is "run". This means we have the ability to branch on future results (or in any case, of the separate, "run" timeline).

[Will Ness]

but for a programmer it means we can program in the EDSL while mixing it with the pure calculations of our pure language. a stack of multilayered sandwiches is a multilayered sandwich. it is that simple.

[Micha Wiedenmann]

In your ; example: What objects/data types does ; map? (Think List maps T to List<T>) How does ; map morphisms/functions between objects/data types? What is pure, join, bind for ;?

[Sandra]

; maps statements i.e. it sequentially applies thunks.

[sergiol]

@jalf Do you have the link? Perhaps you bookmarked it? I just updated the video link in the post because it was dead.