理系学生日記

おまえはいつまで学生気分なのか

問題2-6

自然数だったら数なんて使わずに表せるぜ!!!!って言ってる。

(define zero (lambda (f) (lambda (x) x)))

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

正気の沙汰とはおもえません><。(Church numerals)--。


いちお、(add-1 zero)を置き換えてみるとこうなる。

(add-1 zero)
->(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)))

関数fを何回適用するかで数字を表しているのか!
というわけで、1および2の表現は(add-1)を用いないと、次のようになる。

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

加算は、

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