[Haskell-cafe] Re: State Monad - using the updated state

John Lato jwlato at gmail.com
Thu Jan 8 20:48:49 EST 2009

It sounds like you've got the monadic solution figured out, so that's
good.  Even though I would recommend using State (or StateT if
necessary), I wanted to be sure this question was answered.

> ranq1List :: (Word64 -> a ) -> Word64 -> [a]
> ranq1List converter state = converter newState : ranq1List converter
> newState
>  where
>    newState = ranq1Increment state
> One more question on this - the other concern I had with the recursive list
> approach was that although lazy evaluation prevents me generating numbers
> before I 'ask' for them, I figured that if I was going to be asking for say
> 10 million over the course of one simulation, that although I request them
> one by one, over hours or even days, at the end of the simulation I will
> still have a list of 10 million word64s - each of which I could throw away
> within minutes of asking for it.  This seemed like huge memory bloat, and
> thus probably I was taking the wrong approach.

This "memory bloat" is a space leak.  In general they are to be
avoided.  GHC's garbage collection is quite efficient, so if you
structure your program properly the space will be reclaimed after the
values are used.  Values will only be collected if they cannot be
referenced from live code (just like Java, Python, C#, or other
languages with GC).  If you are able to structure your code like this:

doSomething :: [Word64] -> IO ()
doSomething (rand:rands) = do
  someIO rand
  otherIO rand
  if endFlag then return () else doSomething rands

main = do
  let rands = ranq1List id 1
  doSomething rands

you won't have a space leak.  The head of the list is used within
doSomething, while only the tail is passed in the recursion.  At the
time of the recursive call to doSomething, the head 'rand' value is no
longer accessible by any running code, so it can be GC'd.

Contrast that with this version (somewhat contrived):

doSomething2 :: [Word64] -> Int -> IO ()    -- the Int is an index
into the list.
doSomething2 rands i = do
  let rand = rands !! i
  someIO rand
  otherIO rand
  if endFlag then return () else doSomething2 rands (i + 1)

This version is Really Bad.  Firstly the entire list is passed on each
recursion.  Every element remains within scope, so nothing is GC'd.
That's the space leak.  There's another big problem: the current
random value is computed by traversing from the head of the list.  As
the index value grows, it takes progressively longer to traverse the
list to retrieve the current value.

(N.B. I haven't tested these specific examples, but I think I'm right.)

John Lato

More information about the Haskell-Cafe mailing list