scheme - 如何返回教会号码

Question

我想将十进制编码号更改为 chruch 编码号？

(define (encode n)
  (lambda(fn)(lambda(x) (funPower (fn n)x))))

我的代码有什么问题？谢谢你。

Answer 1

数据结构和硬件决定的教堂号码比二进制号码慢得多。

#lang racket
; church-number->n : procedure -> number
(define (church-number->n cn)
  ((cn (λ (x) (+ 1 x))) 0))

; n->church-number : number -> procedure 
(define (n->church-number n)
  (local [(define zero (λ (f) (λ (x) x)))
          (define add-1
            (lambda (n)
              (lambda (f)
                (lambda (x) (f ((n f) x))))))
          (define (aux n cn)
            (if (= 0 n)
                cn
                (aux (- n 1) (add-1 cn))))]
    (aux n zero)))


;;; TEST
(church-number->n (n->church-number 101)) ; 101
(church-number->n (n->church-number (church-number->n (n->church-number 666)))) ; 666

; still slow than binary number
(church-number->n
 (compose (n->church-number 100) (n->church-number 5))) ; 500

(define mult
  (lambda (m)
    (lambda (n)
      (lambda (f)
        (lambda (x)
          ((m (n f)) x))))))

(church-number->n ((mult (n->church-number 100)) (n->church-number 5))) ; 500

Answer 2

你写了

(define (encode n)
  (lambda(fn)(lambda(x) (funPower (fn n)x))))

假设您已经funPower定义了这样

((funPower fn n) x) = (fn (fn ( ... (fn x) ... )))
;;                    \____n_times____/

（正如我们最近在这里看到的几个这样的问题），你的意思是

(define (encode n)
  (lambda (fn)
    (lambda (x) ((funPower fn n) x))))

即编码n是一个柯里化函数，期望fn然后x，这样

(((encode n) fn) x) = ((funPower fn n) x)
                    = (fn (fn ( ... (fn x) ... )))
;;                    \____n_times____/

所以这只是一个适当的括号问题。

不过，为了提高效率，可以调整该定义，因为

(define (encode n)
  (lambda (fn)
    ((lambda (g)
       (lambda (x) (g x)))
     (funPower fn n))))

(funPower fn n)在收到 之前计算x，而不是每次都为每个新的 重新计算x，这肯定是浪费；这显然等同于

(define (encode n)
  (lambda (fn)
    ((lambda (g)
       g)
     (funPower fn n))))

并且，进一步，只是

(define (encode n)
  (lambda (fn)
    (funPower fn n)))

funPower通过重复平方的幂运算，它本身也可以变得比n项目的线性组合更有效。fn