<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
<title></title>
</head>
<body bgcolor="#ffffff" text="#000000">
Ouch, now I really feel stupid, because I *knew* about the stricter
foldl' version. <br>
<br>
But great to know about the new strictness on vars! I really should get
GHC 6.8 RC1 for Windows...<br>
<br>
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?<br>
<br>
Many thanks,<br>
Peter<br>
<br>
<br>
Bertram Felgenhauer wrote:
<blockquote cite="mid:20071005210350.GA4238@zombie.inf.tu-dresden.de"
type="cite">
<pre wrap="">Peter Verswyvelen wrote:
</pre>
<blockquote type="cite">
<pre wrap="">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?
<a class="moz-txt-link-freetext" href="http://www.haskell.org/haskellwiki/Performance/Strictness">http://www.haskell.org/haskellwiki/Performance/Strictness</a>
</pre>
</blockquote>
<pre wrap=""><!---->
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':
</pre>
<blockquote type="cite">
<pre wrap="">import Data.List
sum' :: Num a => [a] -> a
sum' = foldl' (+) 0
</pre>
</blockquote>
<pre wrap=""><!---->
Arguably this is the "correct" definition of sum. The problem you
had is fairly common.
</pre>
<blockquote type="cite">
<pre wrap="">Why isn't it possible to annotate strictness on the type signature in
Haskell as in Clean? Is this on the TODO list?
</pre>
</blockquote>
<pre wrap=""><!---->
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:
</pre>
<blockquote type="cite">
<pre wrap="">mysum' xs = aux 0 xs
where
aux s (x:xs) = let s' = s+x in s' `seq` aux s' xs
aux s [] = s
</pre>
</blockquote>
<pre wrap=""><!---->
In ghc, you can mark arguments as strict
</pre>
<blockquote type="cite">
<pre wrap="">mysum'' xs = aux 0 xs
where
aux !s (x:xs) = aux (s+x) xs
aux !s [] = s
</pre>
</blockquote>
<pre wrap=""><!---->
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:
</pre>
<blockquote type="cite">
<pre wrap="">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
</pre>
</blockquote>
<pre wrap=""><!---->
Hope that helps,
Bertram
_______________________________________________
Haskell-Cafe mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a>
<a class="moz-txt-link-freetext" href="http://www.haskell.org/mailman/listinfo/haskell-cafe">http://www.haskell.org/mailman/listinfo/haskell-cafe</a>
</pre>
</blockquote>
<br>
</body>
</html>