[Haskell-cafe] Generating a random list

[Kalman Noel]

Milos Hasan wrote:
> 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?

There is, and it has already been mentioned: It's the behaviour of
Prelude.sum that is bugging you. ‘sum’ will build an expression like
this, which is responsible for the stack overflow:

    ((((...(n1 + n2) + n3) + n4) + ...) + nm)
                                        ^ evaluation will start here
               ^ But this is the first addition to be performed

Instead, just use sum', which is defined just like sum, but with a
strict left fold instead of a lazy left fold:

    import Data.List

    sum' :: (Num a) => [a] -> a
    sum' = foldl' (+) 0

I don't know exactly why there is a difference between both programs.  
I suppose that in the first one, the strictness analyzer can optimize
sum into sum', but in the second one it cannot.

Kalman

----------------------------------------------------------------------
Get a free email address with REAL anti-spam protection.
http://www.bluebottle.com/tag/1