(Edited for clarity to more directly address the question.)
Monads and Macros
Monads and macros are different sorts of things. As I'll show below, monad do
notation for the Identity
monad in Haskell is similar to let-rec
in the
desugaring. Then we'll see how the desugaring is not equivalent due to lazy
evaluation in Haskell.
The summary, if you don't care to read any further, is that a macro rewrites
the syntax tree (in Lisps), and in Haskell, monad do
-notation is syntax
sugar. Monads themselves are just types that have an associated dictionary of
functions, so the Identity
monad is not the same as IO
, which is not the
same as STM
or Either
or Cont
.
Does Monad-Do Sequence Expressions?
First, let's assume Lisps and Haskell have the same execution strategy (strict,
call by value). In this assumption, there is not much difference between
Haskell's Monad
do
-notation and the average Lisp's let-rec
. For all of
the Haskell I'm going to be showing, I'm going to have this import statement at
the top:
import Control.Monad.Identity
So, consider the following function:
f :: Identity Int
f = do
a <- return 1
b <- return (a + 1)
c <- return (b + 1)
return c
I am using the Identity monad, which behaves the most similarly to let-rec
.
The do
notation will desugar to this:
fDesugar :: Identity Int
fDesugar =
(return 1 >>= \a ->
(return (a + 1) >>= \b ->
(return (b + 1) >>= \c ->
return c)))
This looks like your Lisp example, but obviously it is using infix notation and
this results in a different sequence of arguments. We can rewrite it to be Lisp
like:
fLisp :: Identity Int
fLisp =
((=<<) (\c -> return c)
((=<<) (\b -> return (b + 1))
((=<<) (\a -> return (a + 1))
(return 1))))
Now, we can "run" this monad using runIdentity
. What does that mean? Why do we
need to "run" monads?
Using Monads
Monads are defined on constructors of types. Some tutorials describe them as
burrito wrappers, but I'm just going to say that a monad can be defined on a lot
of types-that-take-types. One example of a monad is the one I've already used,
Identity
, another monad is IO
. Each of these types is actually a value of
kind * -> *
, that is, it takes a type (of kind *
) and returns a new type. So
a monad is defined for Identity
, which can then be used with Identity Int
,
Identity String
, Identity Foo
, and so on.
Because monads are defined per-type, when evaluating something of type
Identity T
, we need to know how to execute that monad. The sequencing, so to
speak, is dependent on the types.
Identity is a very simple constructor and monad. The constructor is:
newtype Identity a = Identity { runIdentity :: a }
That is, to construct a value of type Identity T
, we just need to pass in a
T
. And to get it out, we just apply runIdentity
to it. That is:
makeIdentity :: a -> Identity a
makeIdentity a = Identity a
runIdentity :: Identity a -> a
runIdentity (Identity a) = a
To understand fLisp
, fDesugar
, or f
, we need to know what >>=
and
return
mean in the context of the Identity
monad:
instance Monad Identity where
return a = Identity a
m >>= k = k (runIdentity m)
With this knowledge, we can derive =<<
for Identity:
k =<< m = k (runIdentity m)
With this in hand, we can rewrite fLisp
, using our definitions. In Haskell
parlance, we are using equational reasoning. We can substitute the left hand
side of our definitions above with the right hand side. So we substitute
(=<<) a b
with a (runIdentity b)
, and return a
with Identity a
:
fLisp' :: Identity Int
fLisp' =
((\c -> Identity c)
(runIdentity ((\b -> Identity (b + 1))
(runIdentity ((\a -> Identity (a + 1))
(runIdentity (Identity 1)))))))
But runIdentity
just strips Identity
from whatever it is applied to. When
runIdentity
is applied to something of the form:
runIdentity ((\a -> Identity (f a)) b)
we can move it inside its argument:
(\a -> runIdentity (Identity a)) b
, and reduce it to (\a -> f a) b
or just
f a
. Let's do all those steps:
fLisp'' :: Identity Int
fLisp'' =
((\c -> Identity c)
(((\b -> (b + 1))
(((\a -> (a + 1))
1)))))
We can finally take the last Identity
out of the first function, and we get:
fLisp''' :: Identity Int
fLisp''' =
Identity
((\c -> c)
(((\b -> (b + 1))
(((\a -> (a + 1))
1)))))
So, clearly Identity
behaves identically to let-rec
, right?
Where Monads Differ
Monads are defined per-type, so Identity
is a lot like your macro let-rec
,
but where the two differ in a critical way is that Haskell does not behave as
we assumed. Haskell does not perform strict, call-by-value evaluation.
We can prove this by writing this in Haskell. blowUp
is a raw error type, when
evaluated it will bubble up an exception and end execution.
blowUp :: a
blowUp = error "I will crash Haskell!"
riskyPair :: (Int, a)
riskyPair = (5, blowUp)
fst' :: (a, b) -> a
fst' = \(a, b) -> a
five :: Int
five = fst' riskyPair
When five
is evaluated, the result is indeed five. Despite it coming from the
tainted value g
, we are able to safely evaluate fst' riskyPair
without
blowing up. Try evaluating riskyPair
though, and you'll see the exception.
Consider the following function g
, it uses the Identity monad, but what does
it do?
g :: Identity Int
g = do
a <- return 1
b <- return (a + 1)
c <- return (b + 1)
d <- return (blowUp)
return c
Curiously, runIdentity g
returns 3
. The same as runIdentity f
.
Monads are not macros, not even the Identity
monad duplicates the behavior of
let-rec
. I tried this in Racket, and I got an error. I could not even compile
the program! Defining g
evaluated the error code.
(define g
(letrec
( (a 1)
(b (+ a 1))
(c (+ b 1))
(d (error "I will crash Racket!"))
) c))
Why Do Monads Differ?
In Haskell, values are lazy in their arguments. If the second value of the pair
is never forced (required) then Haskell will not blow up. And fst f
is "safe"
to execute. In Lisp, values are strict, and g
will always blow up.
Because of Haskell's laziness, many authors will hand-wave monads as the only
way of sequencing operations. This is not strictly true! (No pun intended.)
Monads, then, are not just macros for let-rec
, because the definitions for
>>=
and return
can vary so wildly. We can represent potentially failing
computations with the Either
monad.
I tend to think of monads not as ways of sequencing operations, but more like a
user-defined "semicolon" operator. In some monads (IO
), the act of binding is
a lot like a semi-colon in C or C++. In other monads, the semicolons (binds) do
other things, like chain together error conditions or modify control flow.
See this example
of the Cont
monad for reference. Notice that in this case, inside the Cont
monad, the flow of execution can be altered by statements inside the do
block.