StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POIteration of a randomized algorithm in fixed space and linear time
text
Body
copied!<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) => a -> RMonad a randStep x = do rnd <- 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 -> 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) => Int -> (a -> m a) -> a -> m a iterateM' 0 _ x = return $!! x iterateM' n f x = (f $!! x) >>= iterateM' (n-1) f -- Deeply stict function application. ($!!) :: (NFData a) => (a -> b) -> a -> 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:_) <- liftM (map read) getArgs let start = take size $ repeat 0 rnd <- 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="http://i29.tinypic.com/i59blv.png" rel="nofollow noreferrer">quadratic time per update http://i29.tinypic.com/i59blv.png</a></p> <p>And this is how a heap profile looks:</p> <p><a href="http://i30.tinypic.com/124a8fc.png" rel="nofollow noreferrer">heap profile with -hc http://i30.tinypic.com/124a8fc.png</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>

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