Ladies_Man

Мемоизация результатов вычислений

Dec 26th, 2013
216
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scheme 1.00 KB | None | 0 0
  1. (use-syntax (ice-9 syncase))
  2. (define memoized-factorial
  3.   (let ((l '()))
  4.     (lambda (a)
  5.         (if (<= a 1) 1 (if (assq a l)
  6.                         (cadr (assq a l))
  7.                         (let ((f (* a (memoized-factorial (- a 1)))))
  8.                         (set! l (cons (list a f) l))
  9.                         f))))))
  10.  
  11. (define-syntax lazy-cons
  12.   (syntax-rules ()
  13.     ((lazy-cons a b)
  14.      (cons a (delay b)))))
  15.  
  16. (define (lazy-car p)
  17.   (car p))
  18.  
  19. (define (lazy-cdr p)
  20.   (force (cdr p)))
  21.  
  22. (define (lazy-head xs k)
  23.   (define (iter i xs l)
  24.     (if (= i k)
  25.         l
  26.         (iter (+ i 1) (lazy-cdr xs) (append l (list (lazy-car xs))))))
  27.   (iter 0 xs '()))
  28.  
  29.  
  30. (define (lazy-ref xs k)
  31.   (define (iter i xs)
  32.     (if (= i k)
  33.         (lazy-car xs)
  34.         (iter (+ i 1) (lazy-cdr xs))))
  35.   (iter 0 xs))
  36.  
  37. (define (naturals n)
  38.   (lazy-cons n (naturals (+ n 1))))
  39.  
  40. (define (lazy-f n s)
  41.   (lazy-cons s (lazy-f (+ n 1) (* s (+ n 1)))))
  42.  
  43. (define (lazy-factorial n)
  44.   (lazy-ref (lazy-f 0 1) n))
Advertisement
Add Comment
Please, Sign In to add comment