sicp-ex-1.43

<< Previous exercise (1.42) | sicp-solutions | Next exercise (1.44) >>

Define some primitives:

         (define (square x) (* x x)) 
         (define (compose f g) (lambda (x) (f (g x)))) 

Define the procedure:

 (define (repeat f n) 
    (if (< n 1) 
        (lambda (x) x) 
        (compose f (repeat f (- n 1))))) 

Test with:

         ((repeat square 2) 5) 

Output:

         625 

Another solution using the linear iterative way.

  
 (define (repeat f n) 
   (define (iter n result) 
     (if (< n 1) 
         result 
         (iter (- n 1) (compose f result)))) 
   (iter n identity)) 

Note: This is not linearly iterative as described in the book as a chain of deferred operations is still being built.

The above answer does not follow the book's instructions. The book instructs "Write a procedure that takes as inputs a procedure that computes f and *a positive integer n* and returns the procedure that computes the nth repeated application of f." A correct answer is as follows:

 (define (repeated f n) 
   (lambda (x) (cond ((= n 0) x) 
                     (else 
                      ((compose (repeated f (- n 1)) f) x))))) 

I think the following solution is more elegant. When we only need to apply the function once, we can just return the function (I'm not doing error-checking here to see of n is smaller than 1).

 (define (repeated f n) 
         (if (= n 1) 
                 f 
                 (compose f (repeated f (- n 1))))) 

An extremely succinct solution uses the accumulate procedure defined in 1.32:

 (define (repeated f n) 
   (accumulate compose identity (lambda (i) f) 1 inc n)) 

An solution with O(log n) complexity using compose:

 (define (repeated f n) 
   (cond ((= n 0) identity) 
         ((even? n) (repeated (compose f f) (/ n 2))) 
         (else (compose f (repeated f (- n 1)))))) 

A logarithmic iterative solution.

 (define (lcompose f g) 
   (lambda (x) (g (f x)))) 
  
 (define (identity x) x) 
  
 (define (repeated f n) 
   (define (iter g h m) 
     (cond ((= m 0) g) 
           ((odd? m) (iter (lcompose g h) h (- m 1))) 
           (else (iter g (lcompose h h) (/ m 2))))) 
   (iter identity f n)) 

I personally would rather like to avoid using compose (as the only actual use I see in it would be in the logarithmic solution given above).

 (define (repeated f n) 
         (define (repeated-step counter input) 
                 (if (> counter n) 
                     input 
                     (f (repeated-step (+ counter 1) input)) 
                 ) 
         ) 
         (lambda (x) (repeated-step 1 x)) 
 ) 

What do you guys think about this way of doing it? I believe it generates a linear iterative process:

 (define (repeated f n) 
   (lambda (x) 
     (define (iter n result) 
       (cond ((= n 0) result) 
             ((odd? n) (iter (- n 1) (f result))) 
             (else 
              (iter (- n 2) ((compose f f) result))))) 
     (iter n x))) 
  
  

Is this another correct way of solving? I get the right answer when testing the given example from the book: ((repeated square 2) 5) = 625. I know I'm missing something. New to Scheme and this course, so feedback/criticisms welcomed. Could someone provide a good explanation of this?

 (define (repeated f n) 
   (lambda (x) (f (f x)))) 

^That's not quite right, that just applies f twice. The goal is to apply f n times, as below:

 (repeated f 1) ;; f(x) 
 (repeated f 2) ;; f(f(x)) 
 (repeated f 3) ;; f(f(f(x))) 
 ... 

As a hint, notice how your solution takes n as input and yet doesn't do anything with it in the body - that's a good indicator that something's off.

iterative solution using double with log(n) time complexity

 (define (repeated2-iter f n) 
     (define (iter n current) 
         (cond ((= 1 n) current) 
               ((even? n) (double (iter (/ n 2) current))) 
               (else (compose f (iter (- n 1) (compose f current)))) 
         ) 
     ) 
     (iter n f)     
 ) 

My own solution, that does not use compose. Should be considered silly.

 (define (repeated f n) 
   (if (= n 1) 
       (lambda (x) (f x)) 
       (lambda (x) 
         (f ((repeated f (- n 1)) x))))) 
  
 ((repeated square 2) 5) 

Note: This is not linearly iterative as described in the book as a chain of deferred operations is still being built.

I personally would rather like to avoid using compose (as the only actual use I see in it would be in the logarithmic solution given above).

What do you guys think about this way of doing it? I believe it generates a linear iterative process: