計算機プログラムの構造と解釈（SICP）学習メモ
蒋　いつ峰 2008/09/02   |  プログラミング基礎
第二章　練習2.1～2.6 2008/09/02  |  PK：SICP 練習 2.1～2.6

SICP練習2.1～2.6です。データの抽象。


問題

練習2.1：改善されたmake-rat。
練習2.2：中点を求める。
練習2.3：長方形を表現する。　　→　解答略
練習2.4：略
練習2.5：略
練習2.6：Church数


解答

練習2.1の解答

 
  1. struct rat {  
  2.     int number;  
  3.     int denom;  
  4. }  
  5.   
  6. int gcd(int a, int b) {  
  7.     if (b == 0) {  
  8.         return a;  
  9.     }  
  10.     return gcd(b, a % b);  
  11. }  
  12.   
  13. void printRat(rat x) {  
  14.     Stdout.formatln("{} / {}", x.number, x.denom);  
  15. }  
  16.   
  17. /** 
  18.  * 練習2.1。 
  19.  * 改善されたmake-rat。 
  20.  */  
  21. rat makeRat(int n, int d) {  
  22.     int mul = n * d;  
  23.     rat result;  
  24.     int g = gcd(abs(n), abs(d));     
  25.   
  26.     if (mul > 0) {  
  27.         result.number = abs(n / g);  
  28.         result.denom = abs(d / g);  
  29.     } else {  
  30.         result.number = -1 * abs(n / g);  
  31.         result.denom = abs(d / g);  
  32.     }  
  33.     return result;  
  34. }  

練習2.2の解答

 
  1. /** 
  2.  * 練習2.2。 
  3.  * 中点を求める。 
  4.  */  
  5. struct point {  
  6.     int x;  
  7.     int y;  
  8. }  
  9.   
  10. struct segment {  
  11.     point start;  
  12.     point end;  
  13. }  
  14.   
  15. void printPoint(point p) {  
  16.     Stdout.formatln("({},{})", p.x, p.y);  
  17. }  
  18.   
  19. point midpointSegment(segment s) {  
  20.     point p;  
  21.     p.x = (s.start.x + s.end.x) / 2;  
  22.     p.y = (s.start.y + s.end.y) / 2;  
  23.     return p;  
  24. }  


練習2.6の解答

ポイントはデータを関数として表現。０とは、関数を０回適用、１とは関数を１回適用。頭が痛くなる。。。以下引用です。[1]

; *zero* is a (higher-order) function "(lambda (f) (lambda (x) x)" that
; takes a function as the sole argument (f),
; and returns another function "(lambda (x) x)"
;     which applies f on its sole argument (x) 0 times
; we can see x is actually a dummy...
(define zero
  (lambda (f) (lambda (x) x)))

; we clearly see that, the approach is to represent numbers by functions
; if we apply *number* functions to a function f,
; we get a function that repeatly applies f to its argument *number* times.
; that is, (n f) evaluates to a function which repeatly applies f to its argument n times.
; so ((n f) x) is the result of repeatly applying f to x n times
; (f ((n f) x)) is the result of repeatly applying f to x (n + 1) times

; *add-1* is a (higher-order) function that
; takes a function (representing a number) as the sole argument (n),
; and returns another function (representing a number) "(lambda (f) (lambda (x) (f ((n f) x))))",
;     which takes a function as the sole argument (f),
;     and returns another function "(lambda (x) (f ((n f) x)))",
;         which actually applies f on x (n + 1) times
; so *add-1* returns the function representing n + 1
(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

; if we take the advice and use the substitution model...
; one is (add-1 zero)
(add-1 zero)
(add-1 (lambda (f) (lambda (x) x)))
(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) x)) f) x))))
(lambda (f) (lambda (x) (f ((lambda (x) x) x))))
(lambda (f) (lambda (x) (f x)))

; so one is...
(define one
  (lambda (f) (lambda (x) (f x))))

; and two...
(define two
  (lambda (f) (lambda (x) (f (f x)))))

; and plus...
(define (+ a b)
  (lambda (f) (lambda (x) ((b f) ((a f) x)))))

 [1] http://panxz.blogbus.com/logs/17694897.html

閲覧  |  コメント  |  目次

 
ヘルプ  |  ご利用規約  |  相互リンク  |  問合せ
リンクはご自由に、問合せはお気軽に
©2007 Uprush