PasteRack.org
Paste # 26275
2014-12-13 20:46:54

Fork as a new paste.

Paste viewed 491 times.


Embed:

memeoization

  1. #lang racket
  2. (require racket/match)
  3.  
  4. (define-syntax define-memoized
  5.   (syntax-rules ()
  6.     [(_ (f args ...) bodies ...)
  7.      (define f
  8.        ; store the cache as a hash of args => result
  9.        (let ([results (make-hash)])
  10.          ; need to do this to capture both the names and the values
  11.          (lambda (args ...)
  12.            ((lambda vals
  13.               ; if we haven't calculated it before, do so now
  14.               (when (not (hash-has-key? results vals))
  15.                 (hash-set! results vals (begin bodies ...)))
  16.               ; return the cached result
  17.               (hash-ref results vals))
  18.             args ...))))]))
  19.  
  20. (define-memoized (cPathsR m n)
  21.   (match (list m n)
  22.     [(list 1 _) 1]
  23.     [(list _ 1) 1]
  24.     [(list m n) (+ (cPathsR (sub1 m) n)
  25.                    (cPathsR m (sub1 n)))]))
  26.  
  27. (cPathsR 40 38)

=>

6715886785906254653200