scheme


Church Counter(邱奇计数)

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

我们把zero带入add-1

(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)))

这个时候我们可以和zero比较,就会发现里面多了一次f操作,这就是计数操作

one, two可以写为

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

(add m n)可以写为

(define (add m n) (lambda (f) (lambda (x) ((m f) ((n f) x)))))
comments powered by Disqus