How does this short memoization function in the GHC test suite work? : <p><a href="https://github.com/ryantm/ghc/blob/master/testsuite/tests/simplCore/should_run/simplrun005.hs" rel="noreferrer">Here</a> is the complete runnable code for the following memoization function:</p>

<pre><code>memo f = g
  where
    fz = f Z
    fs = memo (f . S) 
    g  Z    = fz
    g (S n) = fs n
    -- It is a BAD BUG to inline 'fs' inside g
    -- and that happened in 6.4.1, resulting in exponential behaviour

-- memo f = g (f Z) (memo (f . S))
--        = g (f Z) (g (f (S Z)) (memo (f . S . S)))
--        = g (f Z) (g (f (S Z)) (g (f (S (S Z))) (memo (f . S . S . S))))

fib' :: Nat -&gt; Integer
fib'             =  memo fib
  where
  fib Z          =  0
  fib (S Z)      =  1
  fib (S (S n)) = fib' (S n) + fib' n
</code></pre>

<p>I tried to figure it out with expansion of the terms by hand, but that expansion looks just like the slow, unmemoized function. How does it work? And how is the commented out code derived?</p>
