SICPを読む(39) 問題 2.6 Church数

Scheme

わからないときは、わかっている所を書き出そう。

Church数ってなんだ!!

なんとなく掴めた所でコーディング。

まずは定義

Church数を定義すると。

(define zero (lambda (f) (lambda (x) x)))
(define one  (lambda (f) (lambda (x) (f x))))
(define two  (lambda (f) (lambda (x) (f (f x)))))

実行してみると、 #を返すだけで、何をやっているのかわからない。表示できるようにしよう。

(define (inc n)
  (+ n 1))
(define (to-s z)
  ((z inc) 0))

(to-s zero) ; 0
(to-s one)  ; 1
(to-s two)  ; 2

表示できたがイマイチ掴めないので、展開してみる。

(to-s zero)
; zeroを展開
(to-s (lambda (f) (lambda (x) x)))
; to-sを展開
(((lambda (f) (lambda (x) x)) inc) 0)
; incを展開
((lambda (x) x) 0)
0

(to-s one)
(to-s (lambda (f) (lambda (x) (f x))))
(((lambda (f) (lambda (x) (f x))) inc) 0)
((lambda (x) (inc x)) 0)
(inc 0)
1

(to-s two)
(to-s (lambda (f) (lambda (x) (f (f x)))))
(((lambda (f) (lambda (x) (f (f x)))) inc) 0)
((lambda (x) (inc (inc x))) 0)
(inc (inc 0))
(inc 1)
2

はぁはぁ・・・。(incとxは同時に展開した方がわかりやすいかも。)

要するに、1回足す手続きを何回やったか。というのが、Church数。

ここまでは理解した。

add-1を理解する。

add-1が何をやっているのか。理解する事にする。

(define (add-1 n)
  (lambda (f)
    (lambda (x)
      (f ((n f) x)))))

zeroを代入してみると、

(to-s (add-1 zero))
; add-1にzeroを代入
(to-s
    (lambda (f)
      (lambda (x)
        (f ((zero f) x)))))
; fがinc,xが0だから
(inc ((zero inc) 0)) ; ポイント!!
(inc 0)
1

要するに、1回多くincしただけ。ということがわかる。fを1回多く作用させただけ。

おぉ。理解した。

add

これを元にaddを作ろう。

イメージは、

((one inc) ((two inc) 0))

こんな感じ。コーディングすると、

(define (add a b)
  (lambda (f)
    (lambda (x)
      ((a f) ((b f) x)))))

(to-s (add one two)) ; 3

出た!!

つまり、

Church数は、

(define zero   (lambda (f) (lambda (x) x)))
(define one    (lambda (f) (lambda (x) ((zero f) (f x)))))
(define two    (lambda (f) (lambda (x) ((one f)  (f x)))))
(define three  (lambda (f) (lambda (x) ((two f)  (f x)))))

とも書ける訳だ!!

なんかわかってきた!!

まとめ

  • 要は、ある数は、ある関数fを何回xに適用するか、という定義にしてしまうのである。(コピペ)
  • Church数についてはまだまだ理解が足らない。