(sicp37)m3.27

memo化

(define (make-table)
  (let ((table (cons '*table* '())))
    (define (insert! key value)
      (let ((record (assoc key (cdr table))))
        (if record
            (set-cdr! record value)
            (set-cdr! table
                      (cons (cons key value)
                            (cdr table))))))
    (define (lookup key)
      (let ((record (assoc key (cdr table))))
        (if record
            (cdr record)
            #f)))
    (define (inspect) (print (cdr table)))
    (define (dispatch m)
      (cond ((eq? m 'lookup-proc) lookup)
            ((eq? m 'insert-proc!) insert!)
            ((eq? m 'inspect-proc) inspect)))
    dispatch))

(define (lookup key table)
  ((table 'lookup-proc) key))

(define (insert! key value table)
  ((table 'insert-proc!) key value))

(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))))))

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

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