Exercise 3.27.  Memoization (also called tabulation) is a technique that 
enables a procedure to record, in a local table, values that have 
previously been computed. This technique can make a vast difference in 
the performance of a program. A memoized procedure maintains a table in 
which values of previous calls are stored using as keys the arguments 
that produced the values. When the memoized procedure is asked to 
compute a value, it first checks the table to see if the value is 
already there and, if so, just returns that value. Otherwise, it 
computes the new value in the ordinary way and stores this in the table. 
As an example of memoization, recall from section 1.2.2 the exponential 
process for computing Fibonacci numbers:

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

The memoized version of the same procedure is

(define memo-fib
  (memoize (lambda (n)
             (cond ((= n 0) 0)
                   ((= n 1) 1)
                   (else (+ (memo-fib (- n 1))
                            (memo-fib (- n 2))))))))

where the memoizer is defined as

(define (memoize f)
  (let ((table (make-table)))
    (lambda (x)
      (let ((previously-computed-result (lookup x table)))
        (or previously-computed-result
            (let ((result (f x)))
              (insert! x result table)
              result))))))

Draw an environment diagram to analyze the computation of (memo-fib 3). 
Explain why memo-fib computes the nth Fibonacci number in a number of 
steps proportional to n. Would the scheme still work if we had simply 
defined memo-fib to be (memoize fib)?

————————————————————————————————————————————————————————————————————————

When (memo-fib 3) is evaluated, first (memo-fib 2) is evaluated, and the 
result is stored.  This also causes (memo-fib 1) to be calculated and 
stored.  After that, the top-level call calls (memo-fib 1) again, but 
the value is already stored.  For any (memo-fib n), assuming an empty 
table, we have approximately 2*n table lookups, n table insertions, and 
n-1 addition operations, all of which is proportional to n.

Had we simply written (define memo-fib (memoize fib)), this would not 
work since all the internal calls to fib would not be using the memoized 
results.

Interestingly, the (= n 0) and (= n 1) cases will only be hit once, 
since after that they will be memoized.  If there was some way to inject 
these special cases into the memoization table when defining the 
function, we could simplify the code.

let fibs = 0:1: zipWith (+) fibs (tail fibs)