Is there an elegant way to implement this function: `(Monad m) => (s -> a -> m (s, b)) -> s -> [a] -> m [b]`

Question

A function like (Monad m) => (s -> a -> m (s, b)) producing a new state and a new value based on the previous state and the current value is quite frequent.

We can use different approaches for implementing a traversal of a list of a to produce a m [b] given a function f :: s -> a -> m (s, b)

• using Control.Monad.foldM but the code is not particularly nice
• using traverse and a StateT (WriterT m) monad, which is a bit better

Is there a good use of existing libraries to decompose the "state-defined behaviour" with the "output behaviour" of f and get the desired traversal in a few combinators?

Answer 1

Plain StateT suffices,

foo :: Monad m => (s -> a -> m (s, b)) -> s -> [a] -> m [b]
foo g = flip (evalStateT . mapM (StateT . f))
   where
   f a s = liftM swap $ g s a

swap (a,b) = (b,a)   -- or import Data.Tuple

flip and f make the pieces fit, if you must use your exact types instead of the more natural type a -> s -> m (b, s).