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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
