I consider the ListT monad transformer surprisingly tricky. The following implementation that assumes a commutative base monad is hard enough:
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)
It needs applicative to apply the effect of the base monad to the list values. However, the transformer from the list-t package baffles me:
instance Monad m => Monad (ListT m) where
return a =
ListT $ return (Just (a, (ListT (return Nothing))))
(>>=) s1 k2 =
ListT $
uncons s1 >>=
\case
Nothing ->
return Nothing
Just (h1, t1) ->
uncons $ k2 h1 <> (t1 >>= k2)
I am rather bad at reading Haskell code but if we assume Maybe as base monad it seems to me that the bind operation expects a value like (Just 1:2:3:[]):[] for its first argument. Shouldn't it be Just 1:2:3:[]?
This is probably connected to the lazy requirement of ListT in order to respect associativity, but I am not able to put everything together.