[Haskell-cafe] Puzzled

[Bertram Felgenhauer]

Peter Verswyvelen wrote:
> The following code, when compiled with GHC 6.6.1 --make -O gives a stack 
> overflow when I enter 1000000 as a command line argument:
>
> (please don't look at the efficiency of the code, it can of course be 
> improved a lot both in time performance and numeric precision...)
>
> import System
>
> leibnizPI :: Integer -> Double
> leibnizPI n = sum (map leibnizTerm [0..n]) where
>    leibnizTerm n = let i = fromIntegral n
>                in 4 * (((-1) ** i) / (2*i+1))
> main = do
>  args <- getArgs
>  let n = read (head args)
>  print (leibnizPI n)
>
> However, if I replace
>
> main = print (leibnizPI 1000000)
>
> is does not stack overflow.
>
> Now, if I leave the original main, but replace sum in leibnizPI by
>
> mysum xs = aux 0 xs
>    where
>      aux s (x:xs) = aux (s+x) xs
>      aux s [] = s
>
> Then I don't get a stack overflow.
>
> However, I do get a stack overflow when I compile it without -O, in all 
> cases.
>
> This puzzles me. I don't see any non-tail calls in my code...
>
> I guess it has to do with strictness? 
> http://www.haskell.org/haskellwiki/Performance/Strictness

Yes.

The problem is that without optimizations, both  sum  and  mysum
build a large unevaluated expression of the form

    ((..((0+x1)+x2)+...)+xn)

The stack overflow happens when this expression gets evaluated. At that
point, the outermost (+) demands the result of the (+) on the next level,
and so on.

To prevent this you need a stricter version of sum. You can build one
with foldl':

> import Data.List
> 
> sum' :: Num a => [a] -> a
> sum' = foldl' (+) 0

Arguably this is the "correct" definition of sum. The problem you
had is fairly common.

> Why isn't it possible to annotate strictness on the type signature in 
> Haskell as in Clean? Is this on the TODO list?

Strictness is independent from the type in Haskell (but see the fourth
solution presented below). You can explicitely make one value at least
as strict as another using  seq:

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

In ghc, you can mark arguments as strict

> mysum'' xs = aux 0 xs
>    where
>      aux !s (x:xs) = aux (s+x) xs
>      aux !s []     = s

This is a language extension, you need -fbang-patterns
to allow it, or with a recent ghc (6.7, 6.9 or a 6.8 rc)
a {-# LANGUAGE BangPatterns #-} pragma, or -XBangPatterns.

A fourth possibility, which is Haskell 98 again, is to declare an
auxiliary data type with a strict field:

> data Strict a = Strict !a
>
> mysum''' xs = aux (Strict 0) xs
>   where
>     aux (Strict s) (x:xs) = aux (Strict (s+x)) xs
>     aux (Strict s) []     = s

Hope that helps,

Bertram