Memoization involving binomial coefficients

Question

I have a question on how to do a memoization for functions that require two inputs. I have the code for how to do a memoization for something like finding the nth fibonacci number, which I will post here:

(define (fib3 n)
  (local 
    {(define hash identity)
     (define v (make-vector (add1 n) empty))
     (define (get n l) ; num (listof pair) -> false or the pair with n
       (cond
         [(empty? l) false]
         [(= (pair-a (first l)) n) (first l)]
         [else (get n (rest l))]))
     (define (put n r) ; num result -> result
       (begin (vector-set! v (hash n) (cons (make-pair n r) (vector-ref v (hash n))))
              r))
     (define (fib-helper n)
       (match (get n (vector-ref v (hash n)))
         [(struct pair (_ b)) b]
         [false (put n (cond
                         [(= n 0) 1]
                         [(= n 1) 1]
                         [else (+ (fib-helper (- n 1)) (fib-helper (- n 2)))]))]))}
    (fib-helper n)))

However, I am a bit confused on how to implement it for a binomial coefficient function. My normal recursive case looks like this:

(define (comb-recursive m l) (cond [(< m l) 0] [(or (= l 0) (= m l)) 1] [else (+ (comb-recursive (sub1 m) (sub1 l)) (comb-recursive (sub1 m) l))]))

I do not really know how to change this such that it does memoization. Are there any tips that would help me tackle this question and use a format similar to the fib function described above? Thanks in advance!

uselpa uselpa · Accepted Answer · 2014-07-23T10:12:39

1. Your fibonacci example is overly complicated.

The base procedure is:

(define fib
  (lambda (n)
    (cond
      ((= n 0) 1)
      ((= n 1) 1)
      (else  (+ (fib (- n 1)) (fib (- n 2)))))))

To do memoïzation in this function, convert it to something like this:

(define fib
  (let ((cache (make-hash)))
    (lambda (n)
      (or
       (hash-ref cache n #f)
       (let ((res (cond
                    ((= n 0) 1)
                    ((= n 1) 1)
                    (else  (+ (fib (- n 1)) (fib (- n 2)))))))
         (hash-set! cache n res)
         res)))))

Now if you have more than one parameter, your hash key will simply be the list of your parameters, e.g. for (comb-recursive m l) the key to the hash will be the list (m l). The easiest way to get this is do define your procedure as (lambda args ...) - note that there are no parentheses around the parameter args; this means that the actual parameters (one or more) will get bound to a list called args in this case. The real parameters will be destructured later with a match statement, when needed:

(define comb-recursive
  (let ((cache (make-hash)))
    (lambda args ; all arguments are in a list here
      (or
       (hash-ref cache args #f)
       (let ((res (match args
                    ((list m l) ; destructure arguments
                     (cond 
                       [(< m l) 0]
                       [(or (= l 0) (= m l)) 1]
                       [else (+ (comb-recursive (sub1 m) (sub1 l)) 
                                (comb-recursive (sub1 m) l))])))))
         (hash-set! cache args res)
         res)))))

2. Instead of adapting each procedure as needed, you can also use a more general memoïzation procedure that works for any number of parameters. Since it will not know the real number of parameters, instead of using match it will just apply the parameter list:

(define (memoize fn)
  (let ((cache (make-hash)))
    (lambda arg 
      (hash-ref! cache arg (thunk (apply fn arg))))))

It can be used as a generic wrapper around another procedure which doesn't have to be memoïzation-aware.

Example for a fibonacci procedure:

(define fib
  (memoize
   (lambda (n)
     (cond
       ((= n 0) 1) ; based on your example - usually this should be 0?
       ((= n 1) 1)
       (else  (+ (fib (- n 1)) (fib (- n 2))))))))

Applied to your procedure comb-recursive:

(define comb-recursive
  (memoize
   (lambda (m l)
     (cond 
       [(< m l) 0]
       [(or (= l 0) (= m l)) 1]
       [else (+ (comb-recursive (sub1 m) (sub1 l)) 
                (comb-recursive (sub1 m) l))]))))

Memoization involving binomial coefficients

1 Answers