Serendip

Web Studio

問題2.4

置換えモデルを使えば cons がどう働くかがわかりやすい。

(define (cons x y)
  (lambda (m) (m x y)))

(define (car z)
  (z (lambda (p q) p)))

(car (cons x y))
(car (lambda (m) (m x y)))
((lambda (m) (m x y)) (lambda (p q) p))
((lambda (p q) p) x y)
x

cons の定義が理解できれば cdr は car を少し修正するだけで定義できると解る。

(define (cdr z)
  (z (lambda (p q) q)))

(car (cons 2 5))
gosh> 2

(cdr (cons 2 5))
gosh> 5

問題2.5

cons の定義

(define (cons a b)
  (* (expt 2 a) (expt 3 b)))

car は対が2で割り切れなくなるまで2で割る回数を返す。

(define (car c)
  (define (iter x count)
    (if (> (abs (remainder x 2)) 0)
        count
        (iter (/ x 2) (+ count 1))))
  (iter c 0))

cdr は対が3で割り切れなくなるまで3で割る回数を返す。

(define (cdr c)
  (define (iter x count)
    (if (> (abs (remainder x 3)) 0)
        count
        (iter (/ x 3) (+ count 1))))
  (iter c 0))

car と cdr をもう一段抽象化する。

(define (pair c n)
  (define (iter x count)
    (if (> (abs (remainder x n)) 0)
        count
        (iter (/ x n) (+ count 1))))
  (iter c 0))

(define (car c)
  (pair c 2))

(define (cdr c)
  (pair c 3))

(car (cons 2 3))
gosh> 2

(cdr (cons 2 3))
gosh> 3

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る