title: Why would using head/tail instead of pattern matching make evaluation terminate?
body: <p>As an exercise, I'm trying to define a <code>ruler</code> value</p>
  
  <pre><code>ruler :: (Num a, Enum a) =&gt; [a]
  </code></pre>
  
  <p>which corresponds to the ruler function</p>
  
  <pre><code>0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2...
  </code></pre>
  
  <p>where the <code>n</code>'th element of the list (assuming the first element corresponds to <code>n=1</code>) is the largest power of 2 which evenly divides <code>n</code>. To make it more interesting, I'm trying to implement <code>ruler</code> without having to do any divisibility testing.</p>
  
  <p>Using a helper function</p>
  
  <pre><code>interleave :: [a] -&gt; [a] -&gt; [a]
  </code></pre>
  
  <p>which simply alternates the elements from the two given lists, I came up with this - but alas it doesn't work:</p>
  
  <pre><code>interleave :: [a] -&gt; [a] -&gt; [a]
  interleave  (x:xs) (y:ys) = x : y : interleave xs ys
  interleave  _      _      = []
  
  ruler :: (Num a, Enum a) =&gt; [a]
  ruler = foldr1 interleave . map repeat $ [0..]
  
  main :: IO ()
  main = print (take 20 ruler)
  </code></pre>
  
  <p>The program eventually uses up all stack space.</p>
  
  <p>Now, what's strange is that the program works just fine if I adjust the definition of <code>interleave</code> so that it reads</p>
  
  <pre><code>interleave (x:xs) ys = x : head ys : interleave xs (tail ys)
  </code></pre>
  
  <p>I.e. I no longer use pattern matching on the second argument. Why does using <code>head</code> and <code>tail</code> here make <code>ruler</code> terminate - after all, the pattern matching is rather defensive (I only evaluate the first element of the list spine, no?).</p>