[Haskell-cafe] a question about *** Exception: stack overflow ..

[Peter Verswyvelen]

On Thu, Apr 23, 2009 at 9:06 PM, Luke Palmer <lrpalmer at gmail.com> wrote:

> However, there is a function "sum" in the prelude, so you can do this much
> more simply:
>
> sumit :: Int -> Int
> sumit n = sum [1..n]
>
> :-)
>

Yeah, but this prelude sum function suffers from the same stack overflow
thing (which is a design mistake I think):

c:\>ghci
GHCi, version 6.10.2: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude> sum [0..10^6]
*** Exception: stack overflow
Prelude>

So the easiest way to fix this is by defining a strict sum:

import Data.List (foldl')
sum' = foldl' (+) 0

Or if you prefer to see how this works internally:

sum' xs = aux 0 xs
  where
    aux s [] = s
    aux s (x:xs) = let s' = x+s
                   in s' `seq` aux s' xs

An interesting thing I learned from this mailing list is that the stack
overflow does not occur because the huge addition expression
(0+1+2+3+4+5+6+7+...) is build up in memory, but because the evaluation of
this gigantic expression *after* it has been completely build up in memory.

One can demonstrate that the addition expression is first build up in memory
like this:
c:\>ghci
GHCi, version 6.10.2: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude> sum [0..10^100]
<interactive>: out of memory
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090423/d183aa32/attachment.htm