Is there a "chain" monad function in Haskell?

Question

Explain about a "duplicate"

Someone point to Is this a case for foldM? as a possible duplicate. Now, I have a strong opinion that, two questions that can be answered with identical answers are not necessarily duplicates! "What is 1 - 2" and "What is i^2" both yields "-1", but no, they are not duplicate questions. My question (which is already answered, kind of) was about "whether the function iterateM exists in Haskell standard library", not "How to implement a chained monad action".

The question

When I write some projects, I found myself writing this combinator:

repeatM :: Monad m => Int -> (a -> m a) -> a -> m a
repeatM 0 _ a = return a
repeatM n f a = (repeatM (n-1) f) =<< f a

It just performs a monadic action n times, feeding the previous result into the next action. I tried some hoogle search and some Google search, and did not find anything that comes with the "standard" Haskell. Is there such a formal function that is predefined?

Answer 1

You can use foldM, e.g.:

import Control.Monad

f a = do print a; return (a+2)

repeatM n f a0 = foldM (\a _ -> f a) a0 [1..n]

test = repeatM 5 f 3
  -- output: 3 5 7 9 11

Answer 2

Carsten mentioned replicate, and that's not a bad thought.

import Control.Monad
repeatM n f = foldr (>=>) pure (replicate n f)

The idea behind this is that for any monad m, the functions of type a -> m b form the Kleisli category of m, with identity arrows

pure :: a -> m a

(also called return)

and composition operator

(<=<) :: (b -> m c) -> (a -> m b) -> a -> m c
f <=< g = \a -> f =<< g a

Since were actually dealing with a function of type a -> m a, we're really looking at one monoid of the Kleisli category, so we can think about folding lists of these arrows.

What the code above does is fold the composition operator, flipped, into a list of n copies of f, finishing off with an identity as usual. Flipping the composition operator actually puts us into the dual category; for many common monads, x >=> y >=> z >=> w is more efficient than w <=< z <=< y <=< x; since all the arrows are the same in this case, it seems we might as well. Note that for the lazy state monad and likely also the reader monad, it may be better to use the unflipped <=< operator; >=> will generally be better for IO, ST s, and the usual strict state.

Notice: I am no category theorist, so there may be errors in the explanation above.

Answer 3

I find myself wanting this function often, I wish it had a standard name. That name however would not be repeatM - that would be for an infinite repeat, like forever if it existed, just for consistency with other libraries (and repeatM is defined in some libraries that way).

Just as another perspective from the answers already given, I point out that (s -> m s) looks a bit like an action in a State monad with state type s.

In fact, it is isomorphic to StateT s m () - an action which returns no value, because all the work it does is encapsulated in the way it changes the state. In this monad, the function you wanted really is replicateM. You can write it this way in haskell although it probably looks uglier than just writing it directly.

First convert s -> m s to the equivalent form which StateT uses, adding the information-free (), using liftM to map a function over the return type.

> :t \f -> liftM (\x -> ((),x)) . f
\f -> liftM (\x -> ((),x)) . f :: Monad m => (a -> m t) -> a -> m ((), t)

(could have used fmap but the Monad constraint seems clearer here; could have used TupleSections if you like; if you find do notation easier to read it is simply \f s -> do x <- f s; return ((),s) ).

Now this has the right type to wrap up with StateT:

> :t StateT . \f -> liftM (\x -> ((),x)) . f
StateT . \f -> liftM (\x -> ((),x)) . f :: Monad m => (s -> m s) -> StateT s m ()

and then you can replicate it n times, using the replicateM_ version because the returned list [()] from replicateM would not be interesting:

> :t \n -> replicateM_ n . StateT . \f -> liftM (\x -> ((),x)) . f
\n -> replicateM_ n . StateT . \f -> liftM (\x -> ((),x)) . f :: Monad m => Int -> (s -> m s) -> StateT s m ()

and finally you can use execStateT to go back to the Monad you were originally working in:

runNTimes :: Monad m => Int -> (s -> m s) -> s -> m s
runNTimes n act =
  execStateT . replicateM_ n . StateT . (\f -> liftM (\x -> ((),x)) . f) $ act