Kalman Noel kalman.noel at bluebottle.com
Sat Mar 1 05:52:46 EST 2008

```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

```