[Haskell-cafe] Puzzled

[Brent Yorgey]

Just to be clear, I doubt the difference had anything to do with
tail-recursion per se.   My guess is that with the "mysum" version, ghc was
able to do some strictness analysis/optimization that it wasn't able to do
(for whatever reason) with the first version.  The best solution (as others
have pointed out) is to create a strict version of sum with foldl'.

On 10/6/07, Peter Verswyvelen <bf3 at telenet.be> wrote:
>
>  Ouch, now I really feel stupid, because I *knew* about the stricter
> foldl' version.
>
> But great to know about the new strictness on vars! I really should get
> GHC 6.8 RC1 for Windows...
>
> I just got puzzled why mysum worked better than sum for some reason...
> mysym looks like an identical unfolded version of sum to me, yet it behaved
> differently. mysum, also being non-strict, did *not* stack overflow. Maybe
> because it is a simpler / more unfolded version, so it needs to keep less
> euh "unevaluated thunks" (how are these called?) on the stack? So I would
> also have gotten a stack overflow with mysum, it just needed more
> iterations?
>
> Many thanks,
> Peter
>
>
> Bertram Felgenhauer wrote:
>
> 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
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.orghttp://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20071006/2108f8ad/attachment.htm