list monad transformer

[Iavor Diatchki]

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.