On Sat, Mar 1, 2008 at 6:50 AM, Milos Hasan
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. Luke
What is the right way to do this? Sure, I could write my own tail-recursive generator function. But this seems to be an instance of a more general problem - how to avoid algorithms linear in stack space when dealing with large lists.
Thanks a lot! Milos
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe