3 ms·
I had Shriram as a professor - great lecturer. Here's a racket implementation for the memoize function based off of class notes: #lang racket (define memo-tab
by tbenst 14y ago
I had Shriram as a professor - great lecturer. Here's a racket implementation for the memoize function based off of class notes:
#lang racket
(define memo-table (box empty))
(define-struct memo (key ans))
(define (memoize f)
(lambda args
(local ([define lookup (filter (lambda (v)
(equal? args (memo-key v)))
(unbox memo-table))])
(if (empty? lookup)
(begin (local ([define ans (apply f args)])
(begin
(set-box! memo-table (cons (make-memo args ans)
(unbox memo-table)))
ans)))
(memo-ans (first lookup))))))
Edit: I guess HN doesn't like my formatting. Here's a readable version http://pastie.org/4591751 http://pastie.org/4591751
- gus_massa 14y agoYou should use an empty line to make a new paragraph, and then start every line with two spaces: #lang racket (define memo-table (box empty)) (define-struct memo (key ans)) (define (memoize f) (lambda args (local ([define lookup (filter (lambda (v) (equal? args (memo-key v))) (unbox memo-table))]) (if (empty? lookup) (begin (local ([define ans (apply f args)]) (begin (set-box! memo-table (cons (make-memo args ans) (unbox memo-table))) ans))) (memo-ans (first lookup))))))
- Fixnum 14y agoBe careful -- this doesn't fully memoize recursive functions unless you force the computation of intermediate results, since the recursive calls don't use memoization: (define memo-fib (memoize fib)) ;; example from SICP (memo-fib 40) ;; long wait I would love to see a good general-purpose 'memoize but rather doubt it's possible, though I think I remember seeing one in Common Lisp in "Paradigms of Artificial Intelligence Programming" that exploited CL's weird namespacing rules for functions to make recursive functions like 'fib run fast.
- kenko 14y agoYou can solve the problem with the parent's memoization by writing the original fib using open recursion and closing it with a fixed-point operator. Doesn't help for library functions or things like that, though.
- soegaard 14y agohttp://planet.racket-lang.org/package-source/dherman/memoize.plt/3/1/planet-docs/memoize/index.html http://planet.racket-lang.org/package-source/dherman/memoize...