StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POComposing monad actions with folds
text
Body
copied!<p>Let's take a function of type <code>(Monad m) => a -> m a</code>. For example:</p> <pre><code>ghci> let f x = Just (x+1) </code></pre> <p>I'd like to be able to apply it any number of times. The first thing I tried was</p> <pre><code>ghci> let times n f = foldr (>=>) return $ replicate n f </code></pre> <p>The problem is that it won't work for large <code>n</code>:</p> <pre><code>ghci> 3 `times` f $ 1 Just 4 ghci> 1000000 `times` f $ 1 Just *** Exception: stack overflow </code></pre> <p>It doesn't work also the other way:</p> <pre><code>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 </code></pre> <p>Actually, what works is using <code>($!)</code> strictness operator</p> <pre><code>ghci> let timesStrict n f = foldr1 ((>=>) . ($!)) $ replicate n f ghci> 3 `timesStrict` f $ 1 Just 4 ghci> 10000000 `timesStrict` f $ 1 Just 10000001 </code></pre> <p>Is there a nicer or more idiomatic solution? Or probably a stricter one? I still easily get stack overflows if <code>f</code> is a heavy-weight function.</p> <p><em>UPD:</em> I found that writing <code>times</code> 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:</p> <pre><code>times f 0 a = return a times f i a = (f $! a) >>= times f (i - 1) </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload