[Haskell-cafe] Generating a random list

[Luke Palmer]

On Sat, Mar 1, 2008 at 6:50 AM, Milos Hasan <mhasan at cs.cornell.edu> wrote:
> 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 at haskell.org
>  http://www.haskell.org/mailman/listinfo/haskell-cafe
>