<div class="gmail_quote">On Thu, Apr 23, 2009 at 9:06 PM, Luke Palmer <span dir="ltr">&lt;<a href="mailto:lrpalmer@gmail.com" target="_blank">lrpalmer@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

<div class="gmail_quote"><div class="gmail_quote"><div><span style="font-size:small">However, there is a function &quot;sum&quot; in the prelude, so you can do this much more simply:<br></span></div>


<div><br></div><div>sumit :: Int -&gt; Int</div><div>sumit n = sum [1..n]</div><div><br></div><div>:-)</div></div></div></blockquote><div><br></div><div>Yeah, but this prelude <span style="font-style:italic">sum</span> function suffers from the same stack overflow thing (which is a design mistake I think):</div>

<div><br></div><div><div><span style="font-family:&#39;courier new&#39;, monospace">c:\&gt;ghci</span></div><div><span style="font-family:&#39;courier new&#39;, monospace">GHCi, version 6.10.2: <a href="http://www.haskell.org/ghc/" target="_blank">http://www.haskell.org/ghc/</a>  :? for help</span></div>

<div><span style="font-family:&#39;courier new&#39;, monospace">Loading package ghc-prim ... linking ... done.</span></div><div><span style="font-family:&#39;courier new&#39;, monospace">Loading package integer ... linking ... done.</span></div>

<div><span style="font-family:&#39;courier new&#39;, monospace">Loading package base ... linking ... done.</span></div><div><span style="font-family:&#39;courier new&#39;, monospace">Prelude&gt; sum [0..10^6]</span></div>

<div><span style="font-family:&#39;courier new&#39;, monospace">*** Exception: stack overflow</span></div><div><span style="font-family:&#39;courier new&#39;, monospace">Prelude&gt;</span></div>
<div><span style="font-family:&#39;courier new&#39;;font-size:17px"><br></span></div><div><span style="font-size:small">So the easiest way to fix this is by defining a strict sum:</span></div>
<div><span style="font-family:&#39;courier new&#39;;font-size:17px"><br></span></div><div><span style="font-size:small"><span style="font-family:&#39;courier new&#39;, monospace">import Data.List (foldl&#39;)</span></span></div>

<div><span style="font-size:small"><span style="font-family:&#39;courier new&#39;, monospace">sum&#39; = foldl&#39; (+) 0<br><br>Or if you prefer to see how this works internally:<br>
<br>sum&#39; xs = aux 0 xs<br>  where<br>    aux s [] = s<br>    aux s (x:xs) = let s&#39; = x+s </span></span></div><div><span style="font-size:small"><span style="font-family:&#39;courier new&#39;, monospace">                   in s&#39; `seq` aux s&#39; xs</span></span></div>

<div><br></div><div><span style="font-size:small"><span style="font-family:arial, helvetica, sans-serif">An interesting thing I learned from this mailing list is that the stack overflow does not occur because the huge addition expression (0+1+2+3+4+5+6+7+...) is build up in memory, but because the evaluation of this gigantic expression *after* it has been completely build up in memory.</span></span></div>
<div><br></div><div><span style="font-size:small"><span style="font-family:arial, helvetica, sans-serif">One can demonstrate that the addition expression is first build up in memory like this:</span></span></div><div><div>
<span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">c:\&gt;ghci</span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">GHCi, version 6.10.2: <a href="http://www.haskell.org/ghc/">http://www.haskell.org/ghc/</a>  :? for help</span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">Loading package ghc-prim ... linking ... done.</span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">Loading package integer ... linking ... done.</span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">Loading package base ... linking ... done.</span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">Prelude&gt; sum [0..10^100]</span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">&lt;interactive&gt;: <span class="Apple-style-span" style="font-weight: bold;">out of memory</span></span></div><div><br></div></div>
</div></div>