title: Why does adding a polymorphic type signature degrade performance?
body: <p>Here's a simple function to compute Fibonacci numbers:</p>
  
  <pre><code>fib :: [Int]
  fib = 1 : 1 : zipWith (+) fib (tail fib)
  </code></pre>
  
  <p>In ghci I can compute the series quickly. In fact, a bit of experimentation reveals that the computation runs in approximately linear time.</p>
  
  <pre><code>ghci&gt; last $ take 100000 fib
  354224848179261915075         -- takes under a second
  </code></pre>
  
  <p>If I change the type signature to be polymorphic instead:</p>
  
  <pre><code>fib :: Num a =&gt; [a]
  fib = 1 : 1 : zipWith (+) fib (tail fib)
  </code></pre>
  
  <p>Then the algorithm becomes slower. In fact, it seems that it now runs in exponential time!</p>
  
  <p>Does switching to a polymorphic type signature mean that the list being completely recomputed at each stage? If so, why?</p>