From 8df6413225bbc243f3214c5667f468006349fe80 Mon Sep 17 00:00:00 2001 From: Ramakrishnan Muthukrishnan <vu3rdd@gmail.com> Date: Mon, 21 Feb 2011 08:41:41 +0530 Subject: [PATCH] solution to 3.27 --- src/sicp/ex3_27.rkt | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) create mode 100644 src/sicp/ex3_27.rkt diff --git a/src/sicp/ex3_27.rkt b/src/sicp/ex3_27.rkt new file mode 100644 index 0000000..51862b9 --- /dev/null +++ b/src/sicp/ex3_27.rkt @@ -0,0 +1,40 @@ +#lang r5rs + +(define (fib n) + (cond + ((= n 0) 0) + ((= n 1) 1) + (else (+ (fib (- n 1)) + (fib (- n 2)))))) + +(define memo-fib + (memoize (lambda (n) + (cond + ((= n 0) 0) + ((= n 1) 1) + (else (+ (memo-fib (- n 1)) + (memo-fib (- n 2)))))))) + +(define (memoize f) + (let ((previous-output (make-table))) + (lambda (x) + (let ((lookup-result (lookup x previous-output))) + (if lookup-result + lookup-result + (let ((result (f x))) + (insert! x result previous-output) + result)))))) + +#| + +If we define memo-fib as + +(define memo-fib + (memoize fib)) + +and say, call (memo-fib 10), then, we cache the result of calling fib with n=10. +But (fib n) calls (fib (- n 1)) and (fib (- n 2)) and this way of calling memo-fib won't cache those intermediate values. + +On the other hand, if we define memo-fib the way it is defined above, all intermediate calls to memo-fib also goes through memoize call and hence will get cached in the results table. Hence this is much more efficient. + +|# -- 2.45.2