Hatena::Groupcsnagoya-sicp

クラなんとかの日記 このページをアンテナに追加 RSSフィード

 | 

2009-03-31一人準備会などを敢行す

2.6

| 2.6 - クラなんとかの日記 を含むブックマーク はてなブックマーク - 2.6 - クラなんとかの日記 2.6 - クラなんとかの日記 のブックマークコメント

チャーチ数n を,f^n(x) で表現できると仮定する.

(例えば,n=2 のとき,チャーチ数はf^2(x) = f(f(x)) のように表現できる.ということ)

zero は,f^0(x)=x でOK

add-1 は,f^{n+1}(x)=f(f^n(x)) でOK

数学的帰納法より,自然数n はチャーチ数n として表現できる.

ここまでわかれば,one, two の実装はそのままやればよい.

以下では,数値を表示するのに,f=inc を使っている.

inc を n 回適応して,x = 0 とすれば,チャーチ数表現を数値に変換できる.

; -*- coding: utf-8; -*-
; Church numerals

;; 準備

;; 答え
(define one
  (lambda (f)
    (lambda (x)
      (f x))))

(define two
  (lambda (f)
    (lambda (x)
      (f (f x)))))

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

; 問題 2.6 より
(define zero
  (lambda (f)
    (lambda (x)
      x)))

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

;; 確認
(define (display-church n)
  (define (inc x) (+ x 1))
  (display ((n inc) 0)))

(display "zero = ")
(display-church zero) (newline)
(display "one = ")
(display-church one) (newline)
(display "two = ")
(display-church two) (newline)
(display "(+ 1 0) = ")
(display-church (add-1 zero)) (newline)
(display "(+ 1 2) = ")
(display-church (add-1 two)) (newline)
(display "(+ (+ 1 2) 2) = ")
(display-church (plus (add-1 two) two)) (newline)
$ gosh 2.6.scm
zero = 0
one = 1
two = 2
(+ 1 0) = 1
(+ 1 2) = 3
(+ (+ 1 2) 2) = 5
 |