src/sicp/ex3_27.rkt

   1 #lang r5rs
   2
   3 (define (fib n)
   4   (cond
   5     ((= n 0) 0)
   6     ((= n 1) 1)
   7     (else (+ (fib (- n 1))
   8              (fib (- n 2))))))
   9
  10 (define memo-fib
  11   (memoize (lambda (n)
  12              (cond
  13                ((= n 0) 0)
  14                ((= n 1) 1)
  15                (else (+ (memo-fib (- n 1))
  16                         (memo-fib (- n 2))))))))
  17
  18 (define (memoize f)
  19   (let ((previous-output (make-table)))
  20     (lambda (x)
  21       (let ((lookup-result (lookup x previous-output)))
  22         (if lookup-result
  23             lookup-result
  24             (let ((result (f x)))
  25               (insert! x result previous-output)
  26               result))))))
  27
  28 #|
  29
  30 If we define memo-fib as
  31
  32 (define memo-fib
  33   (memoize fib))
  34
  35 and say, call (memo-fib 10), then, we cache the result of calling fib with n=10.
  36 But (fib n) calls (fib (- n 1)) and (fib (- n 2)) and this way of calling memo-fib won't cache those intermediate values.
  37
  38 On the other hand, if we define memo-fib the way it is defined above, all intermediate calls to memo-fib also goes through memoize call and hence will get cached in the results table. Hence this is much more efficient.
  39
  40 |#