186

3
+4  Q:

## Composing monad actions with folds

Let's take a function of type `(Monad m) => a -> m a`. For example:

``````ghci> let f x = Just (x+1)
``````

I'd like to be able to apply it any number of times. The first thing I tried was

``````ghci> let times n f = foldr (>=>) return \$ replicate n f
``````

The problem is that it won't work for large `n`:

``````ghci> 3 `times` f \$ 1
Just 4
ghci> 1000000 `times` f \$ 1
Just *** Exception: stack overflow
``````

It doesn't work also the other way:

``````ghci> let timesl n f = foldl' (<=<) return \$ replicate n f
ghci> 3 `timesl` f \$ 1
Just 4
ghci> 1000000 `timesl` f \$ 1
Just *** Exception: stack overflow
``````

Actually, what works is using `(\$!)` strictness operator

``````ghci> let timesStrict n f = foldr1 ((>=>) . (\$!)) \$ replicate n f
ghci> 3 `timesStrict` f \$ 1
Just 4
ghci> 10000000 `timesStrict` f \$ 1
Just 10000001
``````

Is there a nicer or more idiomatic solution? Or probably a stricter one? I still easily get stack overflows if `f` is a heavy-weight function.

UPD: I found that writing `times` in a pointful form does not solve the problem of composing heavy-weight monadic actions neither. This works for f x = Just (x+1) but fails in the real world:

``````times f 0 a = return a
times f i a = (f \$! a) >>= times f (i - 1)
``````
+1  A:

I came up with this:

`````` last \$ take n \$ iterate (>>= f) \$ Just 1
``````

But it also overflows the stack on large numbers of `n`. I don't have the time right now to look into it more :-(

Anyway, thanks for trying.
+2  A:

I'd probably create some stricter variants of existing functions.

``````{-# LANGUAGE BangPatterns #-}
iterate' f !x = x : iterate' f (f x)
ma >>=! f = do !a <- ma; f a
times' n f a = iterate' (>>=! f) (return a) !! n
``````

Perhaps your problems stem from the fact that `seq` only evaluates the first argument to WHNF? If you're working on a complex structure, you may need a deeper `seq`, like deepseq.

This solution seems to work well, but not better than timesStrict, so it is not scalable neither. I have to look into deepseq. Thank you.
+4  A:

If you make `f` strict as in

``````f x = let y = x+1 in y `seq` Just y
``````

or

``````-- remember to enable -XBangPatterns
f !x = Just (x+1)
``````

and leave the rest alone, your code runs in constant space (albeit slowly) even with very large `n`:

```ghci> times 4000000000 f 3
Just 4000000003```
Well, still the same problem if you run more iterations:ghci> iterateM_n 1000000 (Just . (+1)) 3 \nJust *** Exception: stack overflow \nghci> iterateM_n' 1000000 (+) 0 (Just . (+1)) 3 \nJust *** Exception: stack overflow \n
@jetxee Updated!
I like using `-XBangPatterns` instead of `seq` :-) Anyhow, if `f` is strict then there's no need for `>>=!` in my answer. Since it seems that OP's `f` isn't, this could help.