list monad transformer
Thu, 15 May 2003 11:12:32 -0700
in his thesis , 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 ). 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
 Modular Monadic Semantics and Compilation. Sheng Liang. Ph.D.
Thesis, Yale University, 1997.
 Composing Monads. Mark P. Jones and Luc Duponcheel, Research Report
YALEU/DCS/RR-1004, Yale University, New Haven, Connecticut, USA,