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 <[EMAIL PROTECTED]> 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 > [EMAIL PROTECTED]://www.haskell.org/mailman/listinfo/haskell-cafe > > > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe