Formerly of Apple, I currently write software to solve all manner of interesting problems. I work and live in Coral Gables, FL with my beautiful wife and two kids.
Let's say that one day you wake up and decide that you're tired of always fixing bugs, damnit! So you set out to create a language that won't have bugs. In order to do this, you make your language extremely simple: functions will always take 1 argument, will always return 1 value, and will never have side-effects. You've also heard that types are making a come-back, so this simple language will be statically typed. Just so we can talk more easily about this language, you create a shorthand: a -> a means "a function that takes an argument of type a and returns a value of type a. So a function that sorts a list would look like List -> List.
If you need to pass two arguments, then you will do that by writing a function that takes one argument and returns a function that takes one argument and generates a value. Using our short-hand notation we can write this as a -> b -> a, meaning " a function that takes an argument of type a and returns a function that takes an argument of type b and returns a value of type a. So a function that appends a character to a string would look like String -> Char -> String.
Now that we have a simple notation for our simple language, there's one more thing you want to do to avoid bugs, Tony Hoare's billion-dollar mistake: no null references. So every function must return something.
Great! Now we can start implementing basic functions. Start with add to add two integers. It's signature is Int -> Int -> Int and we use it like so: add 2 3 returns 5. Next, mul also has signature Int -> Int -> Int and mul 2 3 returns 6. Nice! Ok, on to div for division... Ah! But what's this? If we say it's signature is Int -> Int -> Int then what should div 3 0 return?
Crud!
Ok, so we need a type that represents a situation where we can't return a value: Nothing. This doesn't solve our problem completely, though, because we only want div to return Nothing if there's a division by zero. The rest of the time we would like to get back an Int. So we need another new type: Maybe a = Just a | Nothing (types like this are sometimes called a "sum type", "tagged union", "variant", or half-a-dozen other names no one can agree on). This little bit of notation means that any function that has in its signature a Maybe Int can accept either Just Int, which is just an Integer wrapped up to make it compatible with the Maybe type, or Nothing. Now we can write div's type signature as Int -> Int -> Maybe Int.
Problem Solved! ...or is it?
You may have heard rumor of the "Maybe Monad", but this Maybe type we've just described is not yet a monad. A monad requires not only a type but also at least two functions to work on that type. To understand why, consider if you want to start chaining functions in your new minimal language. add (mul 2 3) 4 works and returns 10, since mul turns into an Int after we feed in two Ints and add takes two Ints. But what about mixing in div? We would like add (div 4 2) 1 to return 3, but it won't work because div ends with a Maybe Int and add is expecting an Int.
Time to introduce one more bit of notation to make things a bit easier to talk about: (\x -> f x) indicates an anonymous function that takes an argument x and does something with it (in this case, using it as the argument to a function f).
Ok! Now, the first thing we need is "bind" (just to keep with Haskell notation, let's use >>= for "bind"). This is a function that will know how to take our Maybe type, pull out the value (if there is one) and use it in a function. If there's not a value (that's our Nothing type), then it just passes along Nothing. So, put into our shorthand notation, this looks like:
Justx>>=f=fxNothing>>=_=Nothing
(The _ just means that we don't particularly care what the second argument to "bind" is, because we're always going to return Nothing.)
We're almost there, but there's one more problem. Look what happens if we attempt to combine add and div as before (now using our new anonymous function notation and "bind"):
div42>>=(\x->addx1)
To understand why this is a problem, consider what the type signature of this whole thing should be? If div is returning a Just Int, then that will be passed along to add which will return Int. If, however, we swapped the 2 with a 0 then div would return Nothing and "bind", following our definition above, should return Nothing, which is a Maybe type. So in one case we get an Int and in the other a Maybe...but this is supposed to be a statically typed language!
Crud!
We're almost there. All we need to complete the job is return. This is simply a function that will know how to create an example of our type from some other type. Since Nothing should only ever be used when we don't have a value to return, the definition of return for Maybe a is quite straight-forward: return a = Just a. For other, more complicated types >>= and return could be more complicated.
Finally, now we can combine add and div:
div42>>=(\x->return(addx1))
Et voila! A Maybe monad!
So is a Monad really that simple? Well, yes and no. Much like General Relativity, writing down the basic functions for a Monad isn't all that difficult, but this simple combination of a type and two functions opens a whole world of possibilities for strict, statically typed functional languages. Essentially, Monads allow you to defer some part of your program's evaluation while still writing functions that take one value and return one value. In the case of Maybe, we're deferring what to do about missing values or values that we cannot produce. We can use Monads to defer other things like error handling (the Either Monad) or input (the infamous IO Monad).
Let's say that one day you wake up and decide that you're tired of always fixing bugs, damnit! So you set out to create a language that won't have bugs. In order to do this, you make your language extremely simple: functions will always take 1 argument, will always return 1 value, and will never have side-effects. You've also heard that types are making a come-back, so this simple language will be statically typed. Just so we can talk more easily about this language, you create a shorthand:
a -> a
means "a function that takes an argument of typea
and returns a value of typea
. So a function that sorts a list would look likeList -> List
.If you need to pass two arguments, then you will do that by writing a function that takes one argument and returns a function that takes one argument and generates a value. Using our short-hand notation we can write this as
a -> b -> a
, meaning " a function that takes an argument of typea
and returns a function that takes an argument of typeb
and returns a value of typea
. So a function that appends a character to a string would look likeString -> Char -> String
.Now that we have a simple notation for our simple language, there's one more thing you want to do to avoid bugs, Tony Hoare's billion-dollar mistake: no null references. So every function must return something.
Great! Now we can start implementing basic functions. Start with
add
to add two integers. It's signature isInt -> Int -> Int
and we use it like so:add 2 3
returns5
. Next,mul
also has signatureInt -> Int -> Int
andmul 2 3
returns6
. Nice! Ok, on todiv
for division... Ah! But what's this? If we say it's signature isInt -> Int -> Int
then what shoulddiv 3 0
return?Crud!
Ok, so we need a type that represents a situation where we can't return a value:
Nothing
. This doesn't solve our problem completely, though, because we only wantdiv
to returnNothing
if there's a division by zero. The rest of the time we would like to get back anInt
. So we need another new type:Maybe a = Just a | Nothing
(types like this are sometimes called a "sum type", "tagged union", "variant", or half-a-dozen other names no one can agree on). This little bit of notation means that any function that has in its signature aMaybe Int
can accept eitherJust Int
, which is just an Integer wrapped up to make it compatible with theMaybe
type, orNothing
. Now we can writediv
's type signature asInt -> Int -> Maybe Int
.Problem Solved! ...or is it?
You may have heard rumor of the "Maybe Monad", but this
Maybe
type we've just described is not yet a monad. A monad requires not only a type but also at least two functions to work on that type. To understand why, consider if you want to start chaining functions in your new minimal language.add (mul 2 3) 4
works and returns10
, sincemul
turns into anInt
after we feed in twoInt
s andadd
takes twoInt
s. But what about mixing indiv
? We would likeadd (div 4 2) 1
to return 3, but it won't work becausediv
ends with aMaybe Int
andadd
is expecting anInt
.Time to introduce one more bit of notation to make things a bit easier to talk about:
(\x -> f x)
indicates an anonymous function that takes an argumentx
and does something with it (in this case, using it as the argument to a functionf
).Ok! Now, the first thing we need is "bind" (just to keep with Haskell notation, let's use
>>=
for "bind"). This is a function that will know how to take ourMaybe
type, pull out the value (if there is one) and use it in a function. If there's not a value (that's ourNothing
type), then it just passes alongNothing
. So, put into our shorthand notation, this looks like:(The
_
just means that we don't particularly care what the second argument to "bind" is, because we're always going to returnNothing
.)We're almost there, but there's one more problem. Look what happens if we attempt to combine
add
anddiv
as before (now using our new anonymous function notation and "bind"):To understand why this is a problem, consider what the type signature of this whole thing should be? If
div
is returning aJust Int
, then that will be passed along toadd
which will returnInt
. If, however, we swapped the2
with a0
thendiv
would returnNothing
and "bind", following our definition above, should returnNothing
, which is aMaybe
type. So in one case we get anInt
and in the other aMaybe
...but this is supposed to be a statically typed language!Crud!
We're almost there. All we need to complete the job is
return
. This is simply a function that will know how to create an example of our type from some other type. SinceNothing
should only ever be used when we don't have a value to return, the definition ofreturn
forMaybe a
is quite straight-forward:return a = Just a
. For other, more complicated types>>=
andreturn
could be more complicated.Finally, now we can combine
add
anddiv
:Et voila! A
Maybe
monad!So is a Monad really that simple? Well, yes and no. Much like General Relativity, writing down the basic functions for a Monad isn't all that difficult, but this simple combination of a type and two functions opens a whole world of possibilities for strict, statically typed functional languages. Essentially, Monads allow you to defer some part of your program's evaluation while still writing functions that take one value and return one value. In the case of
Maybe
, we're deferring what to do about missing values or values that we cannot produce. We can use Monads to defer other things like error handling (theEither
Monad) or input (the infamousIO
Monad).This is the best answer so far, thank you for writing this.