title: Tail optimization guarantee - loop encoding in Haskell
body: <p>So the short version of my question is, how are we supposed to encode loops in Haskell, <em>in general</em>? There is no tail optimization guarantee in Haskell, bang patterns aren't even a part of the standard (right?), and fold/unfold paradigm is <em>not</em> guaranteed to work in all situation. Here's <a href="http://rosettacode.org/wiki/Hamming_numbers#Direct_calculation_through_triples_enumeration" rel="nofollow">case in point</a> were only bang-patterns did the trick for me of making it run in constant space (not even using <code>$!</code> helped ... although <a href="http://ideone.com/AkbN1" rel="nofollow">the testing</a> was done at Ideone.com which uses ghc-6.8.2). </p>
  
  <p>It is basically about a nested loop, which in list-paradigm can be stated as</p>
  
  <pre><code>prod (sum,concat) . unzip $ 
      [ (c, [r | t]) | k&lt;-[0..kmax], j&lt;-[0..jmax], let (c,r,t)=...]
  prod (f,g) x = (f.fst $ x, g.snd $ x)
  </code></pre>
  
  <p>Or in pseudocode: </p>
  
  <pre><code>let list_store = [] in
  for k from 0 to kmax
      for j from 0 to jmax
          if test(k,j) 
              list_store += [entry(k,j)]
          count += local_count(k,j)
  result = (count, list_store)
  </code></pre>
  
  <p>Until I added the bang-pattern to it, I got either a memory blow-out or even a stack overflow. But bang patterns are not part of the standard, right? So the question is, <em>how</em> is one to code the above, in standard Haskell, to run in constant space? </p>
  
  <p>Here is <a href="http://ideone.com/uSyGI" rel="nofollow">the test code</a>. The calculation is fake, but the problems are the same. <strong>EDIT:</strong> The <code>foldr</code>-formulated code is:</p>
  
  <pre><code>testR m n = foldr f (0,[]) 
                 [ (c, [(i,j) | (i+j) == d ])
                   | i&lt;- [0..m], j&lt;-[0..n], 
                     let c = if (rem j 3) == 0 then 2 else 1 ]
    where d = m + n - 3
      f (!c1, [])     (!c, h) = (c1+c,h) 
      f (!c1, (x:_))  (!c, h) = (c1+c,x:h)
  </code></pre>
  
  <p><a href="http://ideone.com/RM7qR" rel="nofollow">Trying to run</a> <code>print $ testR 1000 1000</code> produces stack overflow. Changing to <code>foldl</code> only succeeds if using bang-patterns in <code>f</code>, but it builds the list in reversed order. I'd like to build it lazily, and in the right order. Can it be done with any kind of <code>fold</code>, for the <em>idiomatic</em> solution?</p>
  
  <p><strong>EDIT:</strong> to sum up the answer I got from @ehird: there's nothing to fear using bang pattern. Though not in standard Haskell itself it is easily encoded in it as <code>f ... c ... = case (seq c False) of {True -&gt; undefined; _ -&gt; ...}</code>. The lesson is, only pattern match forces a value, and <code>seq</code> does <strong>NOT</strong> force anything by itself, but rather arranges that <em>when</em> <code>seq x y</code> is forced - by a pattern match - <code>x</code> will be forced too, and <code>y</code> will be the answer. Contrary to what I could understand from the Online Report, <code>$!</code> does <strong>NOT</strong> force anything by itself, though it <strong>is</strong> called a <em>"strict application operator"</em>. </p>
  
  <p>And the point from @stephentetley - <em>strictness</em> is very important in controlling the space behaviour. So it is perfectly OK to encode loops in Haskell with proper usage of strictness annotations with bang patterns, where needed, to write any kind of special folding (i.e. structure-consuming) function that is needed - like I ended up doing in the first place - and rely on GHC to optimize the code. </p>
  
  <p>Thank you very much to all for your help.</p>