Tuesday, January 8, 2008

Understanding monads in haskell from a reddit user (808140)

First, thanks to 808140, he did a good job of explaining monads. This is not my content at all, but his.

A quote from reddit, 808140:

"The first step to understanding "monads" is realizing that the name is scary but the concept is simple. See, the term itself comes from math and was so-named because the people that found a use for it in programming were math people. Despite what some people seem to think, though, you don't need to be a math person to understand them.

The best way to grok monads is to not try to understand what they are abstractly first. Instead, familiarize yourself with several common monads and their uses. This will allow you to better see what is being abstracted.

A lot of people who are new to monads try to understand the abstraction before understanding the specific cases. Some people (usually people with math backgrounds) can do this, but for most people, the best way to understand something abstract and general is to start with specific examples.

You can learn what a monad is intuitively very quickly this way, because there are a bunch of things that are all monads but that all do very different things.

The most basic monad is the exception monad (in Haskell we call it Maybe if there's only one exception, and Either if there are many). This is not voodoo. It is no different than throwing an exception in a language you're familiar with, there's nothing new or strange about it. Basically, the code:

f x >>= g >>= h

evaluates f x where f is some function that can throw an exception, checks to see if an exception was thrown, and if it none was, it passes the output of f x into the function g, which can also throw an exception. Again, if g did not throw an exception, it passes the value into h, which itself can throw an exception. Here's an example of what this might be doing. Let's say f, g, and h are all mathematical functions, all of which at some point divide by their argument. Obviously, if the argument is zero, there will be an error, so each checks first if the argument is zero and if it is, each throws an exception, and if not, does the calculation and returns the value. Essentially, this code is the same as what one might write as h(g(f(x))) in another language, but the use of the >>= just makes it clear that we are checking for exceptions.

The reason we go to all this hassle, instead of just having exception throwing built into the language the way you might in Java or most any other imperative language, is because in functional languages functions cannot have side effects. That is, they are completely determined by what they return, and cannot do anything else. They cannot throw exceptions, or print to the screen, or set a global variable, or whatever. This allows something we call referential transparency: if you see f(5) in purely functional code, you should be able to evaluate it once, and take the value it returns and replace every other instance of f(5) in the whole program and have the program run exactly the same way. This is obviously not possible if f, say, prints to the screen (it would only print once, instead of 20 times or whatever). It is also not possible if f throws an exception (what value did it evaluate to? What would you replace other instances of f(5) with?)

So how do exceptions work, then? The same way they work in a language like C, which lacks the ability to throw exceptions as a built in part of the language: they encode the exception as part of the return value. So in our example, f returns just some number or an error value signaling that an exception was thrown. We call this error value Nothing.

So we create a datatype, which we call Maybe, that extends any type (in our example, Integer) so that it includes the value Nothing. We say that a variable of type Maybe Integer can either be Nothing, signifying that an exception was thrown or an error occurred, or it can be just a number, which we indicate by writing Just 5 or Just 10 (the Just is there to remind us that we're dealing with a Maybe type and not just an Integer).

Then the >>= operator is defined thusly. For a function f and maybe type m, if m looks like Just x then m >>= f is the same as f x. That is, the value contained in the Maybe type is just passed into f (other languages might write f(x)).

If, however, m is Nothing, then f is never called and the whole thing just evaluates to Nothing. Since the >>= operator is left associative, just like division or subtraction, we can look at our example this way:

f x >>= g >>= h

first evaluates f x. Maybe it returns Nothing; then by left associativity,

(Nothing >>= g) >>= h
Nothing >>= h

(Referential transparency allows us to reason about our code algebraically, which is why it is good). What if f x didn't throw an exception? Let's say it returns Just 5:

(Just 5 >>= g) >>= h
g 5 >>= h

Now we evaluate g 5. It too can return a value, or it can return Nothing. You can probably see already that if it returns Nothing, the whole expression will evaluate to Nothing. If it doesn't, whatever it returns will be passed on to h, which also has the ability to return Nothing. In this way, we have propagated the error -- which is why functional programmers often talk about exceptions being propagated rather than thrown.

Now, there is one other function that is useful, which I'll call unit (in Haskell, we call it something else, but its name can confuse imperative programmers). unit just takes a normal value and makes it into a Maybe value by putting a Just in front of it:

unit x = Just x

So we could equivalently write the code we wrote before as

unit x >>= f >>= g >>= h

You can think of unit as lifting a normal value into a value that can also throw an exception.

Now, if you've read this far, you've probably noticed that I haven't mentioned monads. Well, Maybe is a monad, a specific example of one that you can use today. unit and >>= are the monad operators (the latter operator is called "bind"). Many different data structures all define unit and bind in completely different ways. All that makes a monad, really, is that you can define two functions like unit and bind on them.

A monad is always a container type, which is to say that like Maybe it extends a simple type like Integer or String by adding some extra information in some way (in our example, we added the possibility of being Nothing, but other monads add other things).

For example, it is possible to write out messages in a purely functional way using a monad. The idea is, instead of just returning a value, you return a value and the string that you want to write to the screen. Why do it that way, instead of just writing out to the screen? Because that way, your functions don't have side-effects, you preserve referential transparency, and you -- and more importantly, your compiler -- can reason about your code algebraically, allowing it to simplify your code the way you would an equation.

I won't go into the gory details regarding this monad (we call it Writer), but the basic idea is this: unit takes a normal value and puts it in a data structure which includes an empty string. Our bind operator evaluates a function, which returns that same kind of data structure, except maybe that structure's string isn't empty (in case you haven't already guessed, the string in question is the string the function "writes" to the screen). It concatenates the two strings and continues on. An example:

unit 5 >>= f >>= g >>= h
(5, "") >>= f >>= g >>= h
f 5 >>= g >> h (message is "")

Assume f 5 evaluates to 3 and writes "f was called\n" (here ++ is the concatenation operator):

(3, "" ++ "f was called\n") >>= g >>= h
g 3 >>= h (message is "f was called\n")

Now g returns 10 and writes out "g was called\n":

(10, "f was called\n" ++
"g was called") >>= h

And h returns 5 and doesn't write out anything:

 h 10 = (5, "f was called\ng was called\n" ++ "")"
= (5, "f was called\ng was called\n")

So here, bind is again passing the value contained in the Writer data structure into the next function, but at the same time it concatenating the messages that each returns.

You can see that these functions are referentially transparent: earlier I said that if f(5) wrote something to the screen, it would not be referentially transparent because you could not evaluate it once and replace every occurence of f(5) with that. But if f uses the Writer monad we just defined, then it is referentially transparent, because its output is contained in its return value.

There are many other monads. The more monads you learn, the more it will become clear what they all have in common; but in the meantime, you can use them productively as you learn them to write purely functional code if you enjoy that sort of thing.

(For the curious: in Haskell, unit is called return. It is nothing like return in C, which is why I did not call it that in this post. It is called unit in category theory, however, so it's not like I just made the name up.)

No comments: