I think this is also covered in "Monad Transformers and Modular Interpreters" [1] (section 7.5), in which the special nature of list monads and their relation to "commutative monads" is called out. I can't pretend to fully understand all that's going on here, but their comments seem to mirror yours. #g -- [1] http://citeseer.nj.nec.com/liang95monad.html At 11:12 15/05/03 -0700, Iavor Diatchki wrote:
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.
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
-------------------
Graham Klyne