[Haskell-cafe] Generating a random list

[Milos Hasan]

Hi, thanks for the reply..
>> Hi,
>>
>>  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..
>>     
>
> Not too likely.  take should not be tail recursive, because that is
> not lazy (you have to compute all n elements to get the first one) and
> thus uses O(n) space, whereas the take in the Prelude is lazy, so uses
> O(1) space.  The prelude take is the one you want.
>
> It's likely that the stack overflow is occurring elsewhere in your
> program.  For example, if you are adding together all the random
> numbers using foldl or foldr, that will eat up your stack (the right
> solution in that case is to use the strict foldl').  Perhaps you could
> post your code, or a minimal example of what you're experiencing
Summing the list works fine, it uses both O(1) stack space and O(1) heap 
space (so the laziness of foldl is not the problem here).

The problem is that I'm not just trying to sum the list, nor any similar 
producer-consumer scenario that could be done in O(1) heap space. What I 
was really trying to do is create a nearest-neighbor search tree with a 
large number of random points. So I really need the list to physically 
materialize in memory, and I don't mind it taking O(N) heap space. The 
problem I was trying to avoid was using O(N) *stack* space in the 
process of creating the list.

Here's a minimal summing example that illustrates the difference. The 
following works fine, since the elements are generated lazily and summed 
on the fly, as expected:

randFloats :: [Float]
randFloats = randoms (mkStdGen 0)

main = do
    let xs = take 1000000 randFloats
    print $ sum xs

But this overflows, because the list is created before being summed, and 
the take function goes into awfully deep recursion:

randFloats :: [Float]
randFloats = randoms (mkStdGen 0)

main = do
    xs <- return $ take 1000000 randFloats
    print $ sum xs

Is there a clean way to avoid this problem?

Thanks,
Milos