CODEWITHSUNDEEP
haskellmonads
Justin L.
Justin L.

Reputation: 13600

Overflow problems in dealing with IO and MonadRandom and chained computations

So basically I have a computation step that takes in a previous result and outputs a Rand g Path, where Path is a custom data type (think of it like a traveling salesman kind of problem). I'm letting MonadRandom handle all of the generator passing and stuff.

I want to find the, say, nth composition of this computation upon itself. Right now I'm using

thecomputation :: (RandomGen g) => Rand g Path
thecomputation = (iterate (>>= step) (return startingPath)) !! n

And then to print it out I would run

main = do
  res <- evalRandIO thecomputation
  print res

However, I have a problem

If I pick a high enough n (i need on the order of 10^6), I get a stack overflow.

I've managed to track the problem to the fact that thecomputation is actually a heavily composed (nested?) IO object. It's a series of IO computations and so ghc has to keep track of all of those layers of nested IO's, and after enough layers, it gives up.

How am I supposed to deal with this? In an imperative language there really isn't much to this. But what should I do here? Should I force some of the IO's to evaluate or ...?

There is a similar question on this site but I wasn't able to get anything helpful out of the accepted answer so I'm still pretty lost

Concrete Example

import System.Random
import Control.Monad.Random
import Control.Monad

data Path = DoublePath Double deriving Show

step :: (RandomGen g) => Path -> Rand g Path
step (DoublePath x) = do
  dx <- getRandom
  return (DoublePath ((x + dx)/x))

thecomputation :: (RandomGen g) => Rand g Path
thecomputation = (iterate (>>= step) (return (DoublePath 10.0))) !! 1000000

main = do
  result <- evalRandIO thecomputation
  print result

does overflow on my computer

Upvotes: 0

Views: 97

Answers (2)

applicative
applicative

Reputation: 8199

It is enough to make the type strict. This ought to be second nature especially for numerical and other 'unboxable' parameters and doesn't require a language extension.

data Path = DoublePath !Double deriving Show

 -- $ ghc -O2 doublepath.hs
 -- ...
 -- $ time ./doublepath
 -- DoublePath 1.526581416150007

 -- real    0m2.516s
 -- user    0m2.307s
 -- sys 0m0.092s

Upvotes: 2

Joachim Breitner
Joachim Breitner

Reputation: 25763

You are bitten by lazyness: Everytime you call step on some value x, GHC is creating a thunk step x that is not evaluated until the final value is required.

A simple fix is to make step strict in its argument, e.g. by pattern-matching on DoublePath !x (and using -XBangPatterns) or inserting x `seq` before the body of the function. Then your code finished without stack overflow (heh).

Upvotes: 3

Related Questions