title: Lazy evaluation of terms in an infinite list in Haskell
body: <p>I am curious about the runtime performance of an infinite list like
  the one below:</p>
  
  <pre><code>fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
  </code></pre>
  
  <p>This will create an infinite list of the fibonacci sequence.</p>
  
  <p>My question is that if I do the following:</p>
  
  <pre><code>takeWhile (&lt;5) fibs
  </code></pre>
  
  <p>how many times does <code>fibs</code> evaluate each term in the list? It seems
  that since <code>takeWhile</code> checks the predicate function for each item in
  the list, the <code>fibs</code> list will evaluate each term multiple times. The
  first 2 terms are given for free. When <code>takeWhile</code> wants to evaluate
  <code>(&lt;5)</code> on the 3rd element, we will get:</p>
  
  <pre><code>1 : 1 : zipWith (+) [(1, 1), (1)] =&gt; 1 : 1 : 3
  </code></pre>
  
  <p>Now, once <code>takeWhile</code> wants to evaluate <code>(&lt;5)</code> on the 4th element: the
  recursive nature of <code>fibs</code> will construct the list again like the
  following:</p>
  
  <pre><code>1 : 1 : zipWith (+) [(1, 2), (2, 3)] =&gt; 1 : 1 : 3 : 5
  </code></pre>
  
  <p>It would seem that the 3rd element needs to be computed again when we
  want to evaluate the value of the 4th element. Furthermore, if the
  predicate in <code>takeWhile</code> is large, it would indicate the function is
  doing more work that is needed since it is evaluating each preceding
  element in the list multiple times. Is my analysis here correct or is
  Haskell doing some caching to prevent multiple evaluations here?</p>