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'.
<br><br><div><span class="gmail_quote">On 10/6/07, <b class="gmail_sendername">Peter Verswyvelen</b> &lt;<a href="mailto:bf3@telenet.be">bf3@telenet.be</a>&gt; wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">



  
  

<div bgcolor="#ffffff" text="#000000">
Ouch, now I really feel stupid, because I *knew* about the stricter
foldl&#39; 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 &quot;unevaluated thunks&quot; (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><span class="sg">
Peter</span><div><span class="e" id="q_11574553cf7cee68_2"><br>
<br>
<br>
Bertram Felgenhauer wrote:
<blockquote type="cite">
  <pre>Peter Verswyvelen wrote:<br>  </pre>
  <blockquote type="cite">
    <pre>The following code, when compiled with GHC 6.6.1 --make -O gives a stack <br>overflow when I enter 1000000 as a command line argument:<br><br>(please don&#39;t look at the efficiency of the code, it can of course be 
<br>improved a lot both in time performance and numeric precision...)<br><br>import System<br><br>leibnizPI :: Integer -&gt; Double<br>leibnizPI n = sum (map leibnizTerm [0..n]) where<br>   leibnizTerm n = let i = fromIntegral n
<br>               in 4 * (((-1) ** i) / (2*i+1))<br>main = do<br> args &lt;- getArgs<br> let n = read (head args)<br> print (leibnizPI n)<br><br>However, if I replace<br><br>main = print (leibnizPI 1000000)<br><br>is does not stack overflow.
<br><br>Now, if I leave the original main, but replace sum in leibnizPI by<br><br>mysum xs = aux 0 xs<br>   where<br>     aux s (x:xs) = aux (s+x) xs<br>     aux s [] = s<br><br>Then I don&#39;t get a stack overflow.<br><br>
However, I do get a stack overflow when I compile it without -O, in all <br>cases.<br><br>This puzzles me. I don&#39;t see any non-tail calls in my code...<br><br>I guess it has to do with strictness? <br><a href="http://www.haskell.org/haskellwiki/Performance/Strictness" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">
http://www.haskell.org/haskellwiki/Performance/Strictness</a>
    </pre>
  </blockquote>
  <pre>Yes.<br><br>The problem is that without optimizations, both  sum  and  mysum<br>build a large unevaluated expression of the form<br><br>    ((..((0+x1)+x2)+...)+xn)<br><br>The stack overflow happens when this expression gets evaluated. At that
<br>point, the outermost (+) demands the result of the (+) on the next level,<br>and so on.<br><br>To prevent this you need a stricter version of sum. You can build one<br>with foldl&#39;:<br><br>  </pre>
  <blockquote type="cite">
    <pre>import Data.List<br><br>sum&#39; :: Num a =&gt; [a] -&gt; a<br>sum&#39; = foldl&#39; (+) 0<br>    </pre>
  </blockquote>
  <pre>Arguably this is the &quot;correct&quot; definition of sum. The problem you<br>had is fairly common.<br><br>  </pre>
  <blockquote type="cite">
    <pre>Why isn&#39;t it possible to annotate strictness on the type signature in <br>Haskell as in Clean? Is this on the TODO list?<br>    </pre>
  </blockquote>
  <pre>Strictness is independent from the type in Haskell (but see the fourth<br>solution presented below). You can explicitely make one value at least<br>as strict as another using  seq:<br><br>  </pre>
  <blockquote type="cite">
    <pre>mysum&#39; xs = aux 0 xs<br>   where<br>     aux s (x:xs) = let s&#39; = s+x in s&#39; `seq` aux s&#39; xs<br>     aux s []     = s<br>    </pre>
  </blockquote>
  <pre>In ghc, you can mark arguments as strict<br><br>  </pre>
  <blockquote type="cite">
    <pre>mysum&#39;&#39; xs = aux 0 xs<br>   where<br>     aux !s (x:xs) = aux (s+x) xs<br>     aux !s []     = s<br>    </pre>
  </blockquote>
  <pre>This is a language extension, you need -fbang-patterns<br>to allow it, or with a recent ghc (6.7, 6.9 or a 6.8 rc)<br>a {-# LANGUAGE BangPatterns #-} pragma, or -XBangPatterns.<br><br>A fourth possibility, which is Haskell 98 again, is to declare an
<br>auxiliary data type with a strict field:<br><br>  </pre>
  <blockquote type="cite">
    <pre>data Strict a = Strict !a<br><br>mysum&#39;&#39;&#39; xs = aux (Strict 0) xs<br>  where<br>    aux (Strict s) (x:xs) = aux (Strict (s+x)) xs<br>    aux (Strict s) []     = s<br>    </pre>
  </blockquote>
  <pre>Hope that helps,<br><br>Bertram<br>_______________________________________________<br>Haskell-Cafe mailing list<br><a href="mailto:Haskell-Cafe@haskell.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">
Haskell-Cafe@haskell.org</a>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://www.haskell.org/mailman/listinfo/haskell-cafe</a>


  </pre>
</blockquote>
<br>
</span></div></div>

<br>_______________________________________________<br>Haskell-Cafe mailing list<br><a onclick="return top.js.OpenExtLink(window,event,this)" href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br><a onclick="return top.js.OpenExtLink(window,event,this)" href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">
http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br><br></blockquote></div><br>