Skip to content

Instantly share code, notes, and snippets.

@cushon

cushon/memo-combinator.ss

Created March 19, 2011 08:45
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save cushon/877342 to your computer and use it in GitHub Desktop.
Save cushon/877342 to your computer and use it in GitHub Desktop.
Download ZIP
Fibonacci implementation using a memoizing y-combinator.
Raw
memo-combinator.ss
(define Y
(λ (f)
(define t (make-hash))
((λ (x) (x x))
(λ (x) (f (λ a (hash-ref! t a (λ () (apply (x x) a)))))))))
(define fib
(Y (λ (f) (λ (n)
(if (< n 2) n
(+ (f (- n 1)) (f (- n 2))))))))
(map fib (build-list 10 add1))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment