[Haskell-cafe] Generating a random list

Milos Hasan mhasan at cs.cornell.edu
Sat Mar 1 03:31:51 EST 2008

Bryan O'Sullivan wrote:
> Milos Hasan wrote:
>> so let's say I want to generate a list of N random floats. The elegant
>> way of doing it would be to create an infinite lazy list of floats and
>> take the first N, but for N = 1,000,000 or more, this overflows the
>> stack. The reason is apparently that the take function is not
>> tail-recursive, and so it uses O(N) stack space..
> You might want to post your code.  The reason take isn't tail recursive
> is that it will be evaluated lazily, so it will not consume O(n) stack
> space.
Yup, see the code I sent to Luke Palmer. The problem is that I really 
need the whole list to do further processing on it, instead of just 
consuming the elements one-by-one as they are produced by the random 
generator. I'm trying to build a search tree, but for simplicity you 
might assume that I just need to sort the list (or any other operation 
that is not a simple fold).

> However, using take is the wrong approach anyway, as the user of the
> random numbers needs to return the unconsumed portion of the list so
> that the next user can consume them.  This is why code that uses random
> numbers is usually written in the context of a state monad, such as
> MonadRandom: http://www.haskell.org/haskellwiki/New_monads/MonadRandom
That sounds interesting, but I'm not sure it's the randomness that's the 
problem here. I could as well have a completely deterministic function f 
:: Int -> Float, and I could try to produce the list "map f 
[1..1000000]", hitting the same issue.


More information about the Haskell-Cafe mailing list