Personal tools

ListT done right

From HaskellWiki

Revision as of 04:36, 7 February 2007 by BrettGiles (Talk | contribs)

Jump to: navigation, search


1 Introduction

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

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

See the #Examples below for demonstrations of these problems.

2 Implementation

The following implemtation 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 (
m [a]
), it lets each element of the list have its own side effects, which only get `excecuted' if this element of the list is really inspected.

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 where
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 
  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 
    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 an
is a sum of two squares. Each inspected possibility is printed, and if the number is indeed a sum of squares, another message is printed. Note that with our ListT, runMyTest only evaluates the side effects needed to find the first representation of
as a sum of squares, which would be impossible with the ListT implementation of
myTest :: 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
A little example session (
is implemented in exactly the same way as
, but uses
*Main> runMyTest 5
Sum of squares.
*Main> runMyTest' 5
Sum of squares.
Sum of squares.

3.2 Grouping effects

I didn't understand the statement "
ListT m
isn't always a monad", even

after I understood why it is too strict. I found the answer in Composing Monads. It's in

fact a direct consequence of the unnecessary strictness.
ListT m

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

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

while test2 returns the answers
. Under the above ListT (if all answers are forced), both return

Andrew Pimlott

3.3 Order of printing

Here is another (simpler?) example showing why "
ListT m
isn't always a monad".
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)
, running
runListT t1
prints "aabbcc", while
runListT t2
instead prints "aabcbc". Under the above ListT, they both print "abc" (if all answers were forced, they would print "abcabc").

Roberto Zunino

4 Relation to Nondet

NonDeterminism describes another monad transformer that can also be used to model nondeterminism. In fact,
are quite similar with the following two functions translating between them
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)
is smaller than
in the sense that
toListT . toNondetT
is the identity (is it ok to call
`retract'?). However, these functions don't define an isomorphism (check for example
NondetT (\_ n -> liftM2 const n n)

Thomas Jaeger

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