[Haskell-cafe] Generating a random list
Milos Hasan
mhasan at cs.cornell.edu
Sat Mar 1 03:18:55 EST 2008
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
More information about the Haskell-Cafe
mailing list