list monad transformer

[Graham Klyne]

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
<GK@NineByNine.org>
PGP: 0FAA 69FF C083 000B A2E9  A131 01B9 1C7A DBCA CB5E