SICP 問題2.4

2017/09/12

#sicp

これは対のもう一つの手続き表現である.
この表現について任意のオブジェクトxとyに対し, (car (cons x y))がxを生じることを証明せよ.

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

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

これに対するcdrの定義は何か.
(ヒント: これが働くことを調べるには, 1.1.5節の置換えモデルを利用せよ.)

(car (cons x y)) は下記のように展開される。

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

cdr の定義

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

テストする。

(define (cons x y)
  (lambda (m) (m x y)))
(define (car z)
  (z (lambda (p q) p)))
(define (cdr z)
  (z (lambda (p q) q)))

;;; test
(car (cons 1 2))
;=> 1
(cdr (cons 1 2))
;=> 2

(car (cons 11 9))
;=> 11
(cdr (cons 11 9))
;=> 9