View source for ListT done right

== Introduction ==

Before transformers-0.6 (e.g. GHC 9.4.x and below), a ListT monad transformer was part of [https://hackage.haskell.org/package/transformers-0.5.6.2/docs/Control-Monad-Trans-List.html Control.Monad.Trans.List]. 
<haskell>
newtype ListT m a = ListT { runListT :: m [a] }

instance (Monad m) => Monad (ListT m) where
    return a = ListT $ return [a]
    m >>= k  = ListT $ do
        a <- runListT m
        b <- mapM (runListT . k) a
        return (concat b)
</haskell>

There are, however, some caveats with this monad transformer.

* <hask>ListT</hask> imposes some strictness that might sometimes be unnecessary.
* <hask>ListT</hask> isn't really a monad transformer, ie. <hask>ListT m</hask> isn't always a monad for a monad <hask>m</hask>. 

See the [[#Examples]] below for demonstrations of these problems and solutions. However, using different monad transformers results in different equational properties. So the key is to think about what you actually want to happen. 

The original <hask>ListT m</hask> is still of use in some situations. For example, if <hask>m</hask> is a probability monad, then <hask>ListT m</hask> is a monad, and comprises the "point processes", a basic idea of statistics. For another example, since the monad laws don't usually hold on-the-nose anyway (see discussion at [[Hask]]), sometimes it doesn't matter that <hask>ListT m</hask> is not a monad on-the-nose, if we're really interested in a quotient structure that is a monad.  

Another point where the original <hask>ListT m</hask> is interesting is that it is a composite of two monads (<hask>m</hask> and the list monad). This leads us to the study of distributive laws. There is a canonical distributive law when <hask>m</hask> is [[Monad#Commutative_monads|commutative]] &mdash; then <hask>ListT m</hask> is a monad.

== 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 (<hask>m [a]</hask>), 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]], the [[Pipes]] package, which provides its own version of ListT and there is the [http://hackage.haskell.org/package/list-t "list-t"] package.

<haskell>
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
</haskell>

== Examples ==

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

=== Sum of squares ===

Here's a silly example how to use ListT. It checks if an <hask>Int</hask> <hask>n</hask> 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 <hask>n</hask> as a sum of squares, which would be impossible with the ListT implementation of <hask>Control.Monad.List.ListT</hask>.

<haskell>
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
</haskell>

A little example session (<hask>runMyTest'</hask> is implemented in exactly the same way as <hask>runMyTest</hask>, but uses <hask>Control.Monad.List.ListT</hask>):

 *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)

=== Grouping effects ===

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

<haskell>
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
</haskell>

Under Control.Monad.List.ListT, test1 returns the answers
<hask>[6,7,8,9,10,11,12,13]</hask> while test2 returns the answers
<hask>[4,5,6,7,10,11,12,13]</hask>.  Under the above ListT (if all answers are forced), both return
<hask>[2,3,5,6,9,10,12,13]</hask>.

[[Andrew Pimlott]]

=== Order of printing ===

Here is another (simpler?) example showing why "<hask>ListT m</hask> isn't always a monad".

<haskell>
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)
</haskell>

Under <hask>Control.Monad.List.ListT</hask>, running <hask>runListT t1</hask> prints "aabbcc", while <hask>runListT t2</hask> instead prints "aabcbc".  Under the above ListT, they both print "abc" (if all answers were forced, they would print "abcabc").

[[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 ==

NonDeterminism describes another monad transformer that can also be used to model nondeterminism. In fact, <hask>ListT</hask> and <hask>NondetT</hask> are quite similar with the following two functions translating between them

<haskell>
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)
</haskell>

<hask>ListT</hask> is smaller than <hask>NondetT</hask> in the sense that <hask>toListT . toNondetT</hask> is the identity (is it ok to call <hask>ListT</hask> `retract'?). However, these functions don't define an isomorphism (check for example <hask>NondetT (\_ n -> liftM2 const n n)</hask>).

[[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]]

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

== References ==

* No-Go Theorems for Distributive Laws. Maaike Zwart and Dan Marsden. LICS 2019 and LMCS 2022. ([https://arxiv.org/abs/2003.12531 arxiv]).

* The MonadBayes library ([https://hackage.haskell.org/package/monad-bayes-0.1.1.0/candidate/docs/Control-Monad-Bayes-Class.html hackage]) is an example of a place that the original <hask>ListT</hask> is used safely. See also Scibior et al., POPL 2017. ([https://arxiv.org/abs/1711.03219 arxiv]). 

* Point processes and probabilistic databases as <hask>ListT Prob</hask> are explored in <i>A monad for point processes</i>, Swaraj Dash and Sam Staton. ACT 2020. ([https://arxiv.org/abs/2101.10479 arxiv]). 


[[Category:Monad]]
[[Category:Proposals]]
[[Category:Nondeterminism]]