(load "table.txt")

(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 (fib n)
  (display "fib ")
  (display n)
  (newline)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))
; 1 ]=> (fib 5)
; fib 5
; fib 3
; fib 1
; fib 2
; fib 0
; fib 1
; fib 4
; fib 2
; fib 0
; fib 1
; fib 3
; fib 1
; fib 2
; fib 0
; fib 1
; ;Value: 5

(define incorrect-memo-fib (memoize fib))
; Memoizing a function in this way memoizes calls from the repl, but does not
; not memoize the recursive calls a function makes to itself.

; 1 ]=> (incorrect-memo-fib 5)
; fib 5
; fib 3
; fib 1
; fib 2
; fib 0
; fib 1
; fib 4
; fib 2
; fib 0
; fib 1
; fib 3
; fib 1
; fib 2
; fib 0
; fib 1
; ;Value: 5
; 
; 1 ]=> (incorrect-memo-fib 5)
; 
; ;Value: 5

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


; 1 ]=> (memo-fib 5)
; memo-fib 5
; memo-fib 3
; memo-fib 1
; memo-fib 2
; memo-fib 0
; memo-fib 4
; ;Value: 5

; In computing fib(n), the lambda is only called n + 1 times before the memo
; contains values of fib for 0 ... n. Each of these calls does constant work
; excluding the recursive calls to itself. This includes at most two calls to
; memo-fib which may be answered in constant time from the memo. Thus the total
; time is O(n).