[Haskell-beginners] [Int] oddness with summing large lists

[Daniel Fischer]

Am Mittwoch 28 April 2010 23:32:10 schrieb Philip Scott:
> Hi all,
>
> I kind of stumbled into this while doing something else - but I thought
> it was worth posting since I have never actually managed to crash ghci
> before :)
>
> Prelude> let d = [1..1000000000000] :: [Int]
> Prelude> sum d
> 0
>
> 0?  I mean, I might have expected an integer overflow, but 0?

I can deduce that you have a 32-bit system (as I do).
Because:

Prelude> 1000000000000 :: Int
-727379968

So ([1 .. 1000000000000] :: [Int]) == [] and sum [] == 0 isn't surprising 
at all.

>
> And now the really odd part... take away one zero
>
> Prelude> let d = [1..100000000000] :: [Int]

Prelude> 100000000000 :: Int
1215752192

, which is a pretty large number. Since you gave the list a name, it stays 
in memory. For each Int in the list, at least 3 machine words are needed 
(one for the Int, pointer from cons-cell to value, pointer to next cons-
cell; actually, I think the overhead is larger), so if you have less than 
14GB of RAM, your ghci can't do it.

> Prelude> sum d
> < ghci crashes and quits >
>
> A slightly more reasonable number..
>
> Prelude> let d = [1..10000000] :: [Int]
> Prelude> sum d
> *** Exception: stack overflow
>
> At least I can appreciate what is going on in this one  :)

That works with

Prelude Data.List> foldl' (+) 0 [1 .. 10000000] :: Int
-2004260032
Prelude Data.List> :set +s
Prelude Data.List> foldl' (+) 0 [1 .. 100000000] :: Int
987459712
(3.47 secs, 4820224616 bytes)
Prelude Data.List> foldl' (+) 0 [1 .. 100000000000] :: Int
2103145472
(44.75 secs, 58584335012 bytes)

>
> I'm aware that this is a silly way to sum from 1 to n, but I am at a
> loss to explain the above behavior (Except the stack overflow, that is
> fair enough).
> I'm also aware that Int is a machine Int, not a clever infinite haskell
> Int.
>
> Any ideas?
>
> All the best,
>
> Phil