具有lambda表达式的阶乘函数

Question

您可以使用lambda表达式自己创建的最透明,最优雅的因子函数是什么？

我的一个学生在伯克利学习了一个Scheme课程,并且给了这个额外的学分问题,即只使用lambda表达式创建阶乘函数(没有定义,让或其他电源程序).我花了一段时间才解决,而且复杂而丑陋.

我现在正在教授Scheme,几年后,我意识到我将把它作为对自己的挑战,并认为其他人也可能会欣赏它.

Answer 1

这是一个(咖喱)版本:

((lambda (x) (x x))
 (lambda (fact-gen)
   (lambda (n)
     (if (zero? n)
         1
         (* n ((fact-gen fact-gen) (sub1 n)))))))

尾递归版:

(let ((fact-gen
       (lambda (fact-gen n acc)
         (if (zero? n)
             acc
             (fact-gen fact-gen (sub1 n) (* n acc))))))
  (lambda (n) (fact-gen fact-gen n 1)))

关于教会数字:

(let* ((one (lambda (s z) (s z)))
       (add1 (lambda (n) (lambda (s z) (s (n s z)))))
       (* (lambda (a b) (lambda (s z) (a (lambda (z2) (b s z2)) z))))
       (cons (lambda (a b) (lambda (f) (f a b)))))
  (lambda (n)
    ((n (lambda (p)
          (p (lambda (count acc)
               (cons (add1 count) (* count acc)))))
        (cons one one))
     (lambda (a b) b))))

Answer 2

我几年前做的一个台词数量是我几年前的两倍，而且更难理解。

(lambda (n)
  ((lambda (fact) (fact fact 1 n))
   (lambda (f P n) (if (<= n 1) P (f f (* n P) (- n 1))))))