如何return堂号

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 是一个 curried 函数 ，期望 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))))

在收到 x 之前计算 (funPower fn n)，而不是每次都为每个新的 x 重新计算，这肯定是浪费； self-evidently 相当于

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

而且，更进一步，

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

funPower 本身也可以比 n 项 fn 的线性组合更有效，方法是通过重复平方 求幂 [=48] =].

如何return堂号

How to return the Church number

scheme

church-encoding

racket