News for hackers. Stuff that matters.
Re:The Racket Blog: Dynamic Programming versus Memoization by tbenst on Sunday August 26, 2012 @11:13AM (#4435238)
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

Re:The Racket Blog: Dynamic Programming versus Memoization by gus_massa on Sunday August 26, 2012 @11:38AM (#4435302)
You 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))))))
Re:The Racket Blog: Dynamic Programming versus Memoization by Fixnum on Sunday August 26, 2012 @12:49PM (#4435462)
Be 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.

Re:The Racket Blog: Dynamic Programming versus Memoization by kenko on Sunday August 26, 2012 @01:01PM (#4435505)
You 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.
Re:The Racket Blog: Dynamic Programming versus Memoization by soegaard on Sunday August 26, 2012 @01:16PM (#4435542)