memoization.rkt

#lang racket

(define-syntax-rule (define/memo (f x ...) e ...)
  (define f
    (let ([m (make-hash)])
      (λ (x ...) (hash-ref! m (list x ...) (λ () e ...))))))

; memoized fibonacci
(define/memo (fib n)
  (if (< n 2) n
      (+ (fib (- n 1)) (fib (- n 2)))))

; memoized ackermann
(define/memo (ack m n)
  (match* (m n)
    [(0 _) (+ n 1)]
    [(_ 0) (ack (- m 1) 1)]
    [(_ _) (ack (- m 1) (ack m (- n 1)))]))

(time (fib 1000))
; result:
; cpu time: 0 real time: 0 gc time: 0
; 434665576869374564356885276750406258025646605173717804024817290895365554179490
; 518904038798400792551692959225930803226347752096896232398733224711616429964409
; 06533187938298969649928516003704476137795166849228875

(time (ack 4 1))
; result:
; cpu time: 204 real time: 203 gc time: 40
; 65533