# list monad transformer

**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:
> import Control.Monad.List
>
> 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 #Identity# monad is commutative
the #ReaderT# transformer preserves commutativity
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.