# ListT done right

### From HaskellWiki

m (typo) |
Petr Pudlak (Talk | contribs) (A pure example where LiftT fails to preserve associativity (but [] is not commutative).) |
||

(8 intermediate revisions by 6 users not shown) | |||

Line 40: | Line 40: | ||

instance Functor m => Functor (ListT m) where |
instance Functor m => Functor (ListT m) where |
||

− | fmap f (ListT m) = ListT $ fmap (fmap f) m where |
+ | fmap f (ListT m) = ListT $ fmap (fmap f) m |

instance Functor m => Functor (MList' m) where |
instance Functor m => Functor (MList' m) where |
||

Line 163: | Line 163: | ||

=== Grouping effects === |
=== Grouping effects === |
||

− | I didn't understand the statement "<hask>ListT m</hask> isn't always a monad", even |
+ | I didn't understand the statement "<hask>ListT m</hask> isn't always a monad", even after I understood why it is too strict. I found the answer in [http://web.cecs.pdx.edu/~mpj/pubs/composing.html Composing Monads]. It's in fact a direct consequence of the unnecessary strictness. <hask>ListT m</hask> is not associative (which is one of the monad laws), because grouping affects when side effects are run (which may in turn affect the answers). Consider |

− | after I understood why it is too strict. I found the answer in |
||

− | [http://www.cse.ogi.edu/~mpj/pubs/composing.html Composing Monads]. It's in |
||

− | fact a direct consequence of the unnecessary strictness. <hask>ListT m</hask> is |
||

− | not associative (which is one of the monad laws), because grouping affects |
||

− | when side effects are run (which may in turn affect the answers). Consider |
||

<haskell> |
<haskell> |
||

+ | import Control.Monad.List |
||

+ | import Data.IORef |
||

+ | |||

test1 :: ListT IO Int |
test1 :: ListT IO Int |
||

− | test1 do |
+ | test1 = do |

r <- liftIO (newIORef 0) |
r <- liftIO (newIORef 0) |
||

(next r `mplus` next r >> next r `mplus` next r) >> next r `mplus` next r |
(next r `mplus` next r >> next r `mplus` next r) >> next r `mplus` next r |
||

Line 198: | Line 201: | ||

t1 :: ListT IO () |
t1 :: ListT IO () |
||

− | t1 = (a `mplus` a >> b) >> c |
+ | t1 = ((a `mplus` a) >> b) >> c |

t2 :: ListT IO () |
t2 :: ListT IO () |
||

− | t2 = a `mplus` a >> (b >> c) |
+ | t2 = (a `mplus` a) >> (b >> c) |

</haskell> |
</haskell> |
||

Line 207: | Line 210: | ||

[[Roberto Zunino]] |
[[Roberto Zunino]] |
||

+ | |||

+ | === Order of <hask>ListT []</hask> === |
||

+ | |||

+ | This is a simple example that doesn't use <hask>IO</hask>, only pure <hask>ListT []</hask>. |
||

+ | <haskell> |
||

+ | v :: Int -> ListT [] Int |
||

+ | v 0 = ListT [[0, 1]] |
||

+ | v 1 = ListT [[0], [1]] |
||

+ | |||

+ | main = do |
||

+ | print $ runListT $ ((v >=> v) >=> v) 0 |
||

+ | -- = [[0,1,0,0,1],[0,1,1,0,1],[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1]] |
||

+ | print $ runListT $ (v >=> (v >=> v)) 0 |
||

+ | -- = [[0,1,0,0,1],[0,1,0,0],[0,1,0,1],[0,1,1,0,1],[0,1,1,0],[0,1,1,1]] |
||

+ | </haskell> |
||

+ | |||

+ | Clearly, <hask>ListT []</hask> fails to preserve the associativity monad law. |
||

+ | |||

+ | This example violates the requirement given in [http://hackage.haskell.org/packages/archive/mtl/latest/doc/html/Control-Monad-List.html the documentation] that the inner monad has to be commutative. However, all the preceding examples use <hask>IO</hask> which is neither commutative, so I suppose this example is valid at the end. Most likely, a proper implementation of <hask>ListT</hask> should not have such a requirement. |
||

+ | |||

+ | --[[User:Petr Pudlak|PetrP]] 19:15, 27 September 2012 (UTC) |
||

== Relation to Nondet == |
== Relation to Nondet == |
||

Line 233: | Line 257: | ||

There's no particular reason why I used fmap, except that the page has the (unfortunate!) title "ListT Done Right", and having Functor superclass of Monad certainly is the right thing. But I agree, that mistake has long been done and I feel my half-hearted cure is worse than the disease. You can find an alternative, more concise definition of a ListT transformer based on even-style lists here: [[ListT done right alternative]] |
There's no particular reason why I used fmap, except that the page has the (unfortunate!) title "ListT Done Right", and having Functor superclass of Monad certainly is the right thing. But I agree, that mistake has long been done and I feel my half-hearted cure is worse than the disease. You can find an alternative, more concise definition of a ListT transformer based on even-style lists here: [[ListT done right alternative]] |
||

+ | |||

+ | [[amb]] has AmbT, which could be considered as 'ListT done right' (since Amb is identical to the list monad). |
||

[[Category:Monad]] |
[[Category:Monad]] |

## Revision as of 19:15, 27 September 2012

## Contents |

## 1 Introduction

The Haskell hierarchical libraries implement a ListT monad transformer. There are, however, some problems with that implementation.

- imposes unnecessary strictness.ListT
- isn't really a monad transformer, ie.ListTisn't always a monad for a monadListT m.m

See the #Examples below for demonstrations of these problems.

## 2 Implementation

The following implementation tries to provide a replacement for the ListT transformer using the following technique. Instead of associating a monadic side effect with a list of values (There is also a ListT done right alternative.

import Data.Maybe import Control.Monad.State import Control.Monad.Reader import Control.Monad.Error import Control.Monad.Cont -- The monadic list type data MList' m a = MNil | a `MCons` MList m a type MList m a = m (MList' m a) -- This can be directly used as a monad transformer newtype ListT m a = ListT { runListT :: MList m a } -- A "lazy" run function, which only calculates the first solution. runListT' :: Functor m => ListT m a -> m (Maybe (a, ListT m a)) runListT' (ListT m) = fmap g m where g MNil = Nothing g (x `MCons` xs) = Just (x, ListT xs) -- In ListT from Control.Monad this one is the data constructor ListT, so sadly, this code can't be a drop-in replacement. liftList :: Monad m => [a] -> ListT m a liftList [] = ListT $ return MNil liftList (x:xs) = ListT . return $ x `MCons` (runListT $ liftList xs) instance Functor m => Functor (ListT m) where fmap f (ListT m) = ListT $ fmap (fmap f) m instance Functor m => Functor (MList' m) where fmap _ MNil = MNil fmap f (x `MCons` xs) = f x `MCons` fmap (fmap f) xs -- Why on earth isn't Monad declared `class Functor m => Monad m'? -- I assume that a monad is always a functor, so the contexts -- get a little larger than actually necessary instance (Functor m, Monad m) => Monad (ListT m) where return x = ListT . return $ x `MCons` return MNil m >>= f = joinListT $ fmap f m instance MonadTrans ListT where lift = ListT . liftM (`MCons` return MNil) instance (Functor m, Monad m) => MonadPlus (ListT m) where mzero = liftList [] (ListT xs) `mplus` (ListT ys) = ListT $ xs `mAppend` ys -- Implemenation of join joinListT :: (Functor m, Monad m) => ListT m (ListT m a) -> ListT m a joinListT (ListT xss) = ListT . joinMList $ fmap (fmap runListT) xss joinMList :: (Functor m, Monad m) => MList m (MList m a) -> MList m a joinMList = (=<<) joinMList' joinMList' :: (Functor m, Monad m) => MList' m (MList m a) -> MList m a joinMList' MNil = return MNil joinMList' (x `MCons` xs) = x `mAppend` joinMList xs mAppend :: (Functor m, Monad m) => MList m a -> MList m a -> MList m a mAppend xs ys = (`mAppend'` ys) =<< xs mAppend' :: (Functor m, Monad m) => MList' m a -> MList m a -> MList m a mAppend' MNil ys = ys mAppend' (x `MCons` xs) ys = return $ x `MCons` mAppend xs ys -- These things typecheck, but I haven't made sure what they do is sensible. -- (callCC almost certainly has to be changed in the same way as throwError) instance (MonadIO m, Functor m) => MonadIO (ListT m) where liftIO = lift . liftIO instance (MonadReader s m, Functor m) => MonadReader s (ListT m) where ask = lift ask local f = ListT . local f . runListT instance (MonadState s m, Functor m) => MonadState s (ListT m) where get = lift get put = lift . put instance (MonadCont m, Functor m) => MonadCont (ListT m) where callCC f = ListT $ callCC $ \c -> runListT . f $ \a -> ListT . c $ a `MCons` return MNil instance (MonadError e m, Functor m) => MonadError e (ListT m) where throwError = lift . throwError {- This (perhaps more straightforward) implementation has the disadvantage that it only catches errors that occur at the first position of the list. m `catchError` h = ListT $ runListT m `catchError` \e -> runListT (h e) -} -- This is better because errors are caught everywhere in the list. (m :: ListT m a) `catchError` h = ListT . deepCatch . runListT $ m where deepCatch :: MList m a -> MList m a deepCatch ml = fmap deepCatch' ml `catchError` \e -> runListT (h e) deepCatch' :: MList' m a -> MList' m a deepCatch' MNil = MNil deepCatch' (x `MCons` xs) = x `MCons` deepCatch xs

## 3 Examples

Here are some examples that show why the old ListT is not right, and how to use the new ListT instead.

### 3.1 Sum of squares

Here's a silly example how to use ListT. It checks if anmyTest :: Int -> ListT IO (Int, Int) myTest n = do let squares = liftList . takeWhile (<=n) $ map (^(2::Int)) [0..] x <- squares y <- squares lift $ print (x,y) guard $ x + y == n lift $ putStrLn "Sum of squares." return (x,y) runMyTest :: Int -> IO (Int, Int) runMyTest = fmap (fst . fromJust) . runListT' . myTest

*Main> runMyTest 5 (0,0) (0,1) (0,4) (1,0) (1,1) (1,4) Sum of squares. *Main> runMyTest' 5 (0,0) (0,1) (0,4) (1,0) (1,1) (1,4) Sum of squares. (4,0) (4,1) Sum of squares. (4,4)

### 3.2 Grouping effects

I didn't understand the statement "import Control.Monad.List import Data.IORef test1 :: ListT IO Int test1 = do r <- liftIO (newIORef 0) (next r `mplus` next r >> next r `mplus` next r) >> next r `mplus` next r test2 :: ListT IO Int test2 = do r <- liftIO (newIORef 0) next r `mplus` next r >> (next r `mplus` next r >> next r `mplus` next r) next :: IORef Int -> ListT IO Int next r = liftIO $ do x <- readIORef r writeIORef r (x+1) return x

Under Control.Monad.List.ListT, test1 returns the answers

### 3.3 Order of printing

Here is another (simpler?) example showing why "a,b,c :: ListT IO () [a,b,c] = map (liftIO . putChar) ['a','b','c'] t1 :: ListT IO () t1 = ((a `mplus` a) >> b) >> c t2 :: ListT IO () t2 = (a `mplus` a) >> (b >> c)

### 3.4 Order of ListT []

This is a simple example that doesn't use v :: Int -> ListT [] Int v 0 = ListT [[0, 1]] v 1 = ListT [[0], [1]] main = do print $ runListT $ ((v >=> v) >=> v) 0 -- = [[0,1,0,0,1],[0,1,1,0,1],[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1]] print $ runListT $ (v >=> (v >=> v)) 0 -- = [[0,1,0,0,1],[0,1,0,0],[0,1,0,1],[0,1,1,0,1],[0,1,1,0],[0,1,1,1]]

--PetrP 19:15, 27 September 2012 (UTC)

## 4 Relation to Nondet

NonDeterminism describes another monad transformer that can also be used to model nondeterminism. In fact,toListT :: (Monad m) => NondetT m a -> ListT m a toListT (NondetT fold) = ListT $ fold ((return.) . MCons) (return MNil) toNondetT :: (Monad m) => ListT m a -> NondetT m a toNondetT (ListT ml) = NondetT (\c n -> fold c n ml) where fold :: Monad m => (a -> m b -> m b) -> m b -> MList m a -> m b fold c n xs = fold' c n =<< xs fold' :: Monad m => (a -> m b -> m b) -> m b -> MList' m a -> m b fold' _ n MNil = n fold' c n (x `MCons` xs) = c x (fold c n xs)

*I propose to replace every occurence of `fmap` in the above code with `liftM`, thereby moving `class Functor` and the complaint about it not being a superclass of `Monad` completely out of the picture. I'd simply do it, if there wasn't this feeling that I have overlooked something obvious. What is it? -- Udo Stenzel*

There's no particular reason why I used fmap, except that the page has the (unfortunate!) title "ListT Done Right", and having Functor superclass of Monad certainly is the right thing. But I agree, that mistake has long been done and I feel my half-hearted cure is worse than the disease. You can find an alternative, more concise definition of a ListT transformer based on even-style lists here: ListT done right alternative

amb has AmbT, which could be considered as 'ListT done right' (since Amb is identical to the list monad).