Composing monad actions with folds
-
19-09-2019 - |
Question
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)
Solution
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
OTHER TIPS
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.
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 :-(