Type of `ListT`-done-right monad transformer

Viewed 162

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.

0 Answers
Related