SICPの問題を解こう20 - ウォンツテック

問題 1.40

fixed-pointを求めるのに $x_{n+1} = f(x_{n})$ を使うのではなくaverage dampingで $x_{n+1} = \frac{x_{n} + f(x_{n})}{2}$ を使う方法もあるがさらに収束が早い方法として $x_{n+1} = x_{n} - \frac{f(x_n)}{f'(x_n)}$ というNewton's methodを使おうという問題。

(define (close-enough? a b)                                                     
  (let ((tolerance 0.0001))                                                     
    (< (abs (- a b)) tolerance)))                                               
(define (fixed-point f first-guess)                                             
  (define (itr x)                                                               
    (let ((next (f x)))                                                         
      (if (close-enough? x next)                                                
          next                                                                  
          (itr next))))                                                         
  (itr first-guess))                                                            
(define (fixed-point-of-transform g transform guess)                            
  (fixed-point (transform g) guess))                                            
(define (newtons-method f)                                                      
  (define (drive f x)                                                           
    (let ((dx 0.0001))                                                          
      (/ (- (f (+ x dx)) (f x)) dx)))                                           
  (lambda (x) (- x (/ (f x) (drive f x)))))                                     
(define (cubic a b c)                                                           
  (lambda (x)                                                                   
    (+ (* x x x) (* a x x) (* b x) c)))                                         
                                                                                
(define (cubic-zero)                                                            
  (fixed-point-of-transform (cubic -2 1 0) newtons-method 1.0))                 
                                                                                
(print (cubic-zero))

問題 1.41

ある手続きを2回繰り返す手続きdoubleを考えた時、(((double (double double)) inc) 5)はどうなるかという問題。doubleで2回なのでincを2回繰り返すのを2回繰り返してさらにそれ全体を2回繰り返すので(2^2)^2回繰り返される。よって5+16。試しにtripleも定義してみた。

(define (double procedure)                                                      
  (lambda (x) (procedure (procedure x))))                                       
(define (triple procedure)                                                      
  (lambda (x) (procedure (procedure (procedure x)))))                           
(define (inc)                                                                   
  (lambda (x) (+ x 1)))                                                         
                                                                                
(print (((double (double double)) (inc)) 5))                                    
(print (((double (double (double double))) (inc)) 5))                           
(print (((triple (triple triple)) (inc)) 5))

結果

21
261
19688

最後のは(3^3)^3 = 19685回繰り返している。

問題 1.42

合成手続き

(define (compose f g)                                                           
  (lambda (x) (f (g x))))                                                       
(define (square x) (* x x))                                                     
(define (inc x) (+ x 1))                                                        
                                                                                
(print ((compose square inc) 6))