#lang racket

#| Problem 1 |#
 ; Define the Fibonacci function fib as usual
 (define (fib n)
 (if (<= n 2) 1
 (+ (fib (- n 1)) (fib (- n 2)))))

; Define the bind
 (define (bind k v al)
 (cons (list k v) al))

; Define the lookup
 (define (lookup k al)
 (if (null? al) #f
 (if (equal? k (car (car al))) (car (cdr (car al)))
 (lookup k (cdr al)))))

; Define a global variable al
 (define al '())

; Define fib_mem
 (define (fib_mem x)
 (let ((res (lookup x al)))
 (cond
 ((equal? res #f) (begin (set! al (bind x (fib x) al))) (fib x))
 (else (begin (display "memoization hit: ")) res)
 )))
 #| Problem 2 |#

(define (build_mem f)
 (let ((local_al '()))
 (lambda (n)
 (let ((res (lookup n local_al)))
 (cond
 ((equal? res #f) (begin (set! local_al (bind n (f n) local_al))) (f n))
 (else (begin (display "memoization hit: ")) res)))
 )
 ))
 ;; Some test case
 (if (= (fib 1) 1) 'pass 'fail)
 (if (= (fib 2) 1) 'pass 'fail)
 (if (= (fib 3) 2) 'pass 'fail)
 (if (= (fib 4) 3) 'pass 'fail)
 (if (= (fib 15) 610) 'pass 'fail)
 (if (= (fib 20) 6765) 'pass 'fail)

(if (equal? (lookup 1 (bind 1 123 al)) 123) 'pass 'fail)
 (if (equal? (lookup 1 (bind 2 123 al)) #f) 'pass 'fail)
 (if (null? al) 'pass 'fail)