How to return the Church number

Question

I want to change decimal encoding number to chruch encoding number ?

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

What's wrong with my code? Thank you.

Answer 1

Data struct and hardware decided church number is so so slower than binary number.

#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

You wrote

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

Assuming you already have funPower defined such that

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

(as we saw several such questions here recently), what you meant was

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

i.e. the encoded n is a curried function, expecting fn and then x, such that

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

So it was just a matter of proper parenthesization.

That definition could be tweaked for efficiency though, as

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

calculating the (funPower fn n) in advance of receiving the x, instead of doing that each time anew for each new x, which is certainly wasteful; which is self-evidently equivalent to

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

and, further, to just

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

funPower itself too could be made more efficient than just linear composition of n items fn, by application of the exponentiation by repeated squaring.