Iavor Diatchki diatchki@cse.ogi.edu
Thu, 15 May 2003 11:12:32 -0700

```hello,

in his thesis [1], sheng liang mentions that we cannot define
a list monad transformer. for some time now i was wondering why is that
but never had the time to look into it, until the other day.
what basically breaks is the associativity law, as the one form
(#lhs# bellow) traverses the "choice tree" in a breadth first search
manner, while the other (#rhs# bellow) does it in a depth first search
manner.  when the underlying monad is not commutative (i.e. the order of
effects in it matters) we run into a probelm.  here is an example:

>
> pr x = lift (putStr \$ show x ++ " ")
>
> test :: (ListT IO (), ListT IO ())
> test = (m >>= f >>= g, m >>= \x -> f x >>= g)
>   where m   = do pr "m: "; pr 1 `mplus` pr 2
>         f _ = do pr "f: "; pr 3 `mplus` pr 4
>         g _ = do pr "g: "; pr 5 `mplus` pr 6
>
> main = do let (lhs,rhs) = test
>           runListT lhs
>           putStrLn ""
>           runListT rhs

the transformer will work for commutative monads (intuition is above,
formal proof is in [2]).  given that, we should either remove the
#ListT# transformer from the monad library, or (perhaps better) put a
big warning that it should only be used with commutative monads.
a rule of thumb for determining the commutativity of a monad is (using
terminology from the library):
the #ErrorT# transformer preserves commutativity
the #WriterT# transformer preserves commutativity if its monoid (for
collecitng output) is commutative

bye
iavor

References
==========

[1] Modular Monadic Semantics and Compilation. Sheng Liang. Ph.D.
Thesis, Yale University, 1997.
[2] Composing Monads. Mark P. Jones and Luc Duponcheel, Research Report
YALEU/DCS/RR-1004, Yale University, New Haven, Connecticut, USA,
December 1993.

```