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.