How to combine List and State Monad in Haskell

Question

I want to basically map over a list and at the same time carry along some state. I figured combining the list and state monads might get me there. I tried a few things and figured out that I likely need to use ListT for that. As a simplified version of my actual problem, imagine that I want to implement the sum function, while also returning a modified version of the original list. This or similar is what I imagined it would have to look like:

sum' :: ListT (State Int) Int
sum' = do
    lift $ put 0
    x <- [1,2,3]
    lift $ modify (+x)
    return $ x + 1

What I don't get yet is how the syntax of the regular list monad translates to the ListT monad. I cannot simply do x <- [1,2,3], since on the right side of the arrow, type ListT (State Int) t0 is expected. x <- return [1,2,3] compiles (as in keeps the compiler from complaining about this line) but gets me the whole list put into x, instead of each element.

How do I get this working?

Do you want ssum xs = execState (traverse (modify . (+)) xs) 0? — user3237465
Unfortunately, whenever anyone talks about ListT, you really have to ask "which one?" because there are several very different versions that behave very differently. — dfeuer

leftaroundabout leftaroundabout · Accepted Answer · 2015-10-04T11:40:36

    x <- ListT $ return [1,2,3]

or

    x <- msum $ return <$> [1,2,3]

will do the trick.

ListT . return just injects a list structure-awarely into a list-transformed monad stack.
msum uses the fact that ListT is the transformer mapping a monad to the free MonadPlus monoid over it.

How to combine List and State Monad in Haskell

1 Answers