title: Iteration of a randomized algorithm in fixed space and linear time
body: <p>I used to ask a similar question <a href="https://stackoverflow.com/questions/2236829/composing-monad-actions-with-folds">once</a>. Now I'll be more specific. The purpose is to learn a Haskell idiom to write iterative algorithms with monadic results. In particular, this might be useful for implementing all kinds of randomized algorithms, such as genetic algorithms and a like.</p>
  
  <p>I wrote an example program that manifests my problem with such algorithms in Haskell. Its complete source is on <a href="http://hpaste.org/fastcgi/hpaste.fcgi/view?id=27398#a27398" rel="nofollow noreferrer">hpaste</a>.</p>
  
  <p>The key point is to update an element randomly (thus the result is in <code>State StdGen</code> or some other monad):</p>
  
  <pre><code>type RMonad = State StdGen
  
  -- An example of random iteration step: one-dimensional random walk.
  randStep :: (Num a) =&gt; a -&gt; RMonad a
  randStep x = do
    rnd &lt;- get
    let (goRight,rnd') = random rnd :: (Bool, StdGen)
    put rnd'
    if goRight
       then return (x+1)
       else return (x-1)
  </code></pre>
  
  <p>And then one needs to update many elements, and repeat the process many, many times. And here is a problem.  As every step is a monad action (<code>:: a -&gt; m a</code>), repeated many times, it's important to compose such actions effectively (forgetting the previous step quickly). From what I learned from my previous quesion <a href="https://stackoverflow.com/questions/2236829/composing-monad-actions-with-folds">(Composing monad actions with folds)</a>,  <code>seq</code> and <code>deepseq</code> help a lot to compose monadic actions. So I do:</p>
  
  <pre><code>-- Strict (?) iteration.
  iterateM' :: (NFData a, Monad m) =&gt; Int -&gt; (a -&gt; m a) -&gt; a -&gt; m a
  iterateM' 0 _ x = return $!! x
  iterateM' n f x = (f $!! x) &gt;&gt;= iterateM' (n-1) f 
  
  -- Deeply stict function application.
  ($!!) :: (NFData a) =&gt; (a -&gt; b) -&gt; a -&gt; b
  f $!! x = x `deepseq` f x
  </code></pre>
  
  <p>It is certainly better than lazy composition. Unfortunately, it is not enough.</p>
  
  <pre><code>-- main seems to run in O(size*iters^2) time...
  main :: IO ()
  main = do
    (size:iters:_) &lt;- liftM (map read) getArgs
    let start = take size $ repeat 0
    rnd &lt;- getStdGen
    let end = flip evalState rnd $ iterateM' iters (mapM randStep) start
    putStr . unlines $ histogram "%.2g" end 13
  </code></pre>
  
  <p>When I measured time required to finish this program, it appears, that it is similar to O(N^2) with respect to the number of iterations (memory allocation seems to be acceptable). This profile should be flat and constant for linear asymptotics:</p>
  
  <p><a href="https://i.stack.imgur.com/KEVaI.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/KEVaI.png" alt="quadratic time per update"></a>
  </p>
  
  <p>And this is how a heap profile looks:</p>
  
  <p><a href="https://i.stack.imgur.com/76osE.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/76osE.png" alt="heap profile with -hc"></a>
  </p>
  
  <p>I assume that such a program should run with very modest memory requirements, and it should take time proportional to the number of iterations. How can I achieve that in Haskell?</p>
  
  <p>The complete runnable source of the example is <a href="http://hpaste.org/fastcgi/hpaste.fcgi/view?id=27398#a27398" rel="nofollow noreferrer">here</a>.</p>