title: Strange space behavior of Haskell program
body: <p>I thought that the <code>Cont</code> monad is just equivalent to CPS Transformation, so if I have 
  a monadic sum, if I run in the <code>Identity</code> monad, it will fail due to stack overflow, and if
  I run it in the <code>Cont</code> Monad, it will be okay due to tail recursion.</p>
  
  <p>So I've written a simple program to verify my idea. But to my surprise, the result is unreasonable due to my limited knowledge.</p>
  
  <p>All programs are compiled using <code>ghc --make Test.hs -o test &amp;&amp; ./test</code></p>
  
  <pre><code>sum0 n = if n==0  then  0  else n + sum0 (n-1)
  sum1 n = if  n==0  then return 0 else sum1 (n-1) &gt;&gt;= \ v -&gt;  seq v (return (n+v))
  sum2 n k = if n == 0 then k 0 else sum2 n (\v -&gt; k (n + v))
  sum3 n k = if n == 0 then k 0 else sum3 n (\ !v -&gt; k (n + v))
  sum4 n k = if n == 0 then k 0 else sum4 n (\ v -&gt; seq v ( k (n + v)))
  sum5 n = if  n==0  then return 0 else sum5 (n-1) &gt;&gt;= \ v -&gt;   (return (n+v)) 
  </code></pre>
  
  <ul>
  <li><p><code>main = print (sum0 3000000)</code><br>
  Stack overflow. This is reasonable. </p></li>
  <li><p><code>main = print (flip runCont id (sum1 3000000))</code><br>
  Uses 180M memory, which is reasonable, but I am not clear why <code>seq</code> needed here, since its continuation is not applied until <code>n</code> goes to 0.</p></li>
  <li><p><code>main = print (flip runCont id (sum5 3000000))</code><br>
  Stack overflow. Why?                         </p></li>
  <li><p><code>main = print (flip runCont (const 0) (sum1 3000000))</code><br>
  Uses 130M memory. This is reasonable.</p></li>
  <li><p><code>main = print (flip runCont (const 0) (sum5 3000000))</code><br>
  Uses 118M memory. This is reasonable.  </p></li>
  <li><p><code>main = print (sum2 3000000 (const 0))</code><br>
  Uses a lot of memory (more than 1G). I thought <code>sum2</code> is equivalent to <code>sum5</code> (when <code>sum5</code> is in <code>Cont</code> monad). Why?</p></li>
  <li><p><code>main = print (sum3 3000000 (const 0))</code><br>
  Uses a lot of memory. I thought <code>sum3</code> is equivalent to <code>sum1</code> (<code>Cont</code> monad). Why?                                                                                                   </p></li>
  <li><p><code>main = print (runIdentity (sum1 3000000))</code><br>
  Stack overflow, exactly what I want.</p></li>
  <li><p><code>main = print (sum3 3000000 id)</code><br>
  Uses a lot of memory. Equivalent to <code>sum1</code>, why?                                                                                                           </p></li>
  <li><p><code>main = print (sum4 3000000 id)</code><br>
  Uses a lot of memory. Equivalent to sum1, why?</p></li>
  <li><p><code>main = print (sum [1 .. 3000000])</code><br>
  Stack overflow. The source of <code>sum = foldl (+) 0</code>, so this is reasonable.</p></li>
  <li><p><code>main = print (foldl' (+) 0 [1 .. 3000000])</code><br>
  Uses 1.5M.</p></li>
  </ul>