Sat Jul 23 13:28:51 CEST 2011

Monads and evaluation order

The name Monad refers to "1 output"[1].  This output is referred to as
a parametric type (M t).

The interesting thing is that while bind takes functions that produces
a single monadic (wrapped) _output_ from from a single naked input,
there is no reason that functions could not be partially applied
functions.  However, trying to do this immediately raises the issue of
order, i.e. for partial application of a function of type:

   bind2 :: M a -> M b -> (a -> b -> M c) -> M c

there are 2 natural implementations that have some symmetry but have a
different behaviour, becuse one bind operator is "executed first":

  bind2 ma mb f =
    ma >>= \a ->
    mb >>= \b -> f a b

  bind2' ma mb f =
    mb >>= \b ->
    ma >>= \a -> f a b

The same, but in do notation:

  bind2 ma mb f = do
    a <- ma
    b <- mb
    f a b

  bind2' ma mb f = do
    b <- mb
    a <- ma
    f a b

From the significance of the order of lines in the do statement (or
equivalently, the data dependency of the application of >>= operators)
it seems plausible to accept that monads can be used for implementing
behaviour that requires a certain order, i.e. state updates or CPS

Note that there are monads for which the order does not matter.  These
are called commutative monads[2].

[1] http://www.haskell.org/haskellwiki/Monad
[2] http://www.haskell.org/haskellwiki/Monad#Commutative_monads