sicp-ex-4.21



<< Previous exercise (4.20) | Index | Next exercise (4.22) >>


meteorgan

  
  
  
 ;; a 
  (lambda (n)  
    ((lambda (fib) 
       (fib fib n)) 
     (lambda (f n) 
       (cond ((= n 0) 0) 
             ((= n 1) 1) 
             (else (+ (f f (- n 2)) (f f (- n 1)))))))) 
  
 ;; b. filling the box as sequence: 
 ev? od? (- n 1) 
 ev? od? (- n 1) 

Rptx

  
  
  
 ;; a  
 ; this fib procedure uses the iterative version of fib. 
 ((lambda (n) 
    ((lambda (fib) 
       (fib fib 1 0 n)) 
     (lambda (fib a b count) 
       (if (= count 0) 
           b 
           (fib fib (+ a b) a (- count 1)))))) 
  10) 

As suspected from the recursive process minus recursive function, and confirmed through the footnote, this is a rather roundabout example of Haskell Curry's famous Y Combinator.

I couldn't figure out what they were getting at with the even/odd example, but here's a clearer version of what's going on in the factorial example:

  
 ;non-recursive factorial function 
 (define fact-once 
    (lambda (f) 
      (lambda (n) 
        (if (= n 0) 
            1 
            (* n (f (- n 1))))))) 
  
 ;y-combinator 
 (define Y  
   (lambda (f) 
     ((lambda (x) (x x)) 
      (lambda (x) (f (lambda (y) ((x x) y))))))) 
  
 (define factorial (Y fact-once)) 
 (factorial 20)  ;=2432902008176640000