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.
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
G'day all. On Thu, May 15, 2003 at 11:12:32AM -0700, Iavor Diatchki wrote:
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.
My personal choice would be to dump it and replace it with Ralf Hinze's backtracking monad transformer, which _does_ preserve commutativity. If someone with checkin rights is listening in, I'd be very happy to contribute my implementation, which is about as stable as it's ever going to be. Cheers, Andrew Bromage
G'day all.
On Thu, May 15, 2003 at 11:12:32AM -0700, Iavor Diatchki wrote:
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.
My personal choice would be to dump it and replace it with Ralf Hinze's backtracking monad transformer, which _does_ preserve commutativity. If someone with checkin rights is listening in, I'd be very happy to contribute my implementation, which is about as stable as it's ever going to be.
hello, in my earlier post i made a silly mistake -- i said that #ErrorT# preserves commutativity, which is definately wrong throwError 1 >> throwError 2 /= throwError 2 >> throwError 1 (what was i thinking :-) Andrew J Bromage wrote: that's an interesting idea, i'd forgotten about that one. by the way it is not that the list monad transformer does not preserve commutativity, it simply does not produce a monad when transforming a non-commutative monad. bye iavor
participants (4)
-
Andrew J Bromage -
Graham Klyne -
Iavor Diatchki -
Iavor S. Diatchki