title: Reasoning about performance in Haskell
body: <p>The following two Haskell programs for computing the n'th term of the Fibonacci sequence have greatly different performance characteristics:</p>
  
  <pre><code>fib1 n =
    case n of
      0 -&gt; 1
      1 -&gt; 1
      x -&gt; (fib1 (x-1)) + (fib1 (x-2))
  
  fib2 n = fibArr !! n where
    fibArr = 1:1:[a + b | (a, b) &lt;- zip fibArr (tail fibArr)]
  </code></pre>
  
  <p>They are very close to mathematically identical, but <code>fib2</code> uses the list notation to memoize its intermediate results, while <code>fib1</code> has explicit recursion.  Despite the potential for the intermediate results to be cached in <code>fib1</code>, the execution time gets to be a problem even for <code>fib1 25</code>, suggesting that the recursive steps are always evaluated.  Does referential transparency contribute anything to Haskell's performance?  How can I know ahead of time if it will or won't?</p>
  
  <p>This is just an example of the sort of thing I'm worried about.  I'd like to hear any thoughts about overcoming the difficulty inherent in reasoning about the performance of a lazily-executed, functional programming language.</p>
  
  <hr>
  
  <p><strong>Summary:</strong>  I'm accepting 3lectrologos's answer, because the point that you don't reason so much about the language's performance, as about your compiler's optimization, seems to be extremely important in Haskell - more so than in any other language I'm familiar with.  I'm inclined to say that the importance of the compiler is the factor that differentiates reasoning about performance in lazy, functional langauges, from reasoning about the performance of any other type.</p>
  
  <hr>
  
  <p><strong>Addendum:</strong> Anyone happening on this question may want to look at <A HREF="http://blog.johantibell.com/2010/09/slides-from-my-high-performance-haskell.html" rel="nofollow noreferrer">the slides</A> from <A HREF="http://blog.johantibell.com/" rel="nofollow noreferrer">Johan Tibell</A>'s <A HREF="http://cufp.org/conference/sessions/2010/high-performance-haskell" rel="nofollow noreferrer">talk about high performance Haskell</A>.</p>