title: When does GHC use sharing?
body: <p>A beginner's question. I am a bit confused about the following: I read that GHC's (Haskell's?) lazy evaluation method includes the use of sharing, so for example evaluating the expression</p>
  
  <p><code>(1+1)*(1+1)</code></p>
  
  <p>will only compute <code>1+1</code> once. In the book "Programming in Haskell" by Graham Hutton, it is explained that this is realized by replacing both occurences of <code>1+1</code> by a pointer to one copy of it and evaluating just that one copy.</p>
  
  <p>But computing the nth Fibonacci number by <code>fib n = if (n&lt;2) then n else fib (n-1) + fib(n-2)</code> takes exponential time in n. My undestanding of the above tells me that for example <code>fib 5</code> will be evaluated like this:</p>
  
  <p><code>fib 5 =&gt; fib 4 + fib 3 =&gt; fib 3 + fib 2 + fib 3 =&gt; x + fib 2 + x</code></p>
  
  <p>with <code>x = fib 3 = fib 2 + fib 1 = y + fib 1</code></p>
  
  <p>so <code>fib 5 = y + fib 1 + y + y + fib 1</code></p>
  
  <p>with <code>y = fib 2 = fib 1 + fib 0 = 1</code></p>
  
  <p>so <code>fib 5 = 1 + 1 + 1 + 1 + 1</code></p>
  
  <p>where <code>x</code> and <code>y</code> were introduced as shared values.</p>
  
  <p>But this way of proceeding, while somewhat less efficient than the standard way of iteratively generating <code>fib k</code> for <code>2&lt;=k&lt;=n</code>, clearly would not result in such a long running time as evaluating the function in fact does. So what's wrong with my understanding?   </p>