您可以仅使用 lambda 表达式自行创建的最透明、最优雅的阶乘函数是什么？
我的一个学生在伯克利参加了一个计划课程，并获得了仅使用 lambda 表达式（没有定义、let 或其他幂过程）创建阶乘函数的额外学分问题。我花了一段时间才解决，而且很复杂而且丑陋。
几年后，我现在正在教授Scheme，我意识到我要把它作为对自己的挑战，并认为其他人也可能会欣赏它。
这是一个（柯里化的）版本：
((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))))
这是我能想到的最简单的尾递归版本：
(lambda (n)
(((lambda (!) (! !))
(lambda (!)
(lambda (n acc)
(if (zero? n)
acc
((! !) (sub1 n) (* n acc))))))
n 1))
在较小的空间内很难实现递归。自应用程序必须发生在某个地方，并且大多数按值调用语言（如Scheme）中的独立固定点都必须引入额外的 lambda 以避免自应用程序中的失控递归。
相反，我的解决方案和 Jeremiah 的解决方案将自我应用程序隐藏在Scheme短路的一个分支中
if我几年前做的一个有两倍的台词，而且更难理解。
(lambda (n)
((lambda (fact) (fact fact 1 n))
(lambda (f P n) (if (<= n 1) P (f f (* n P) (- n 1))))))
这是我之前在使用 Y-Combinator 时编写的代码。
[λ (n)
;; Y combinator (specialized to two arguments)
(([λ (rec-func)
([λ (procedure)
(rec-func [λ (arg1 arg2) ((procedure procedure) arg1 arg2)])]
[λ (procedure)
(rec-func [λ (arg1 arg2) ((procedure procedure) arg1 arg2)])])]
;; The factorial function (tail recursive)
[λ (func-arg)
[λ (n tot)
(if (zero? n)
tot
(func-arg (- n 1) (* n tot)))]])
n 1)]
我首先在无类型 lambda 演算中编写解决方案，使用诸如 zero?、true、false 等内容的顶级定义，使用 Church 编码定义。此实现假设多参数函数是柯里化的并且函数是部分应用的（如 Haskell）。
Church 编码自然数看起来像：
(define 0 λf x. x)
(define 1 λf x. f x)
(define 2 λf x. f (f x))
(define 3 λf x. f (f (f x)))
教会布尔值
truefalse(define const λx y. x)
(define U λf. f f)
(define true λt f. t)
(define false λt f. f)
(define succ λn f x. f (n f x))
(define 0 λf x. x)
(define * λm n f x. m (n f) x)
(define zero? λn. n (const false) true)
(define pred λn f x. n (λg h. h (g f)) (const x) id)
定义了这些先决条件后，现在我们使用自应用递归来定义阶乘函数。这个定义是尾递归的。
(define !
U (lambda loop acc n.
zero? n -- branches wrapped in lambdas
-- to accomodate call-by-value
(lambda _. acc)
(lambda _. (loop loop (* n acc) (pred n))))
n) -- dummy argument to evaluate selected branch
1)
从这里开始，我作弊并在
!U这是由此产生的术语。它相当神秘（尽管如果没有翻译，我很难用手写出这么短的东西），所以我添加了注释来标识我仍然可以识别的部分。
(λx. x x) -- self application
(λloop acc n.
n (λy t f. f) -- const false
(λt f. t) -- true
(λ_. acc) -- zero? branch
(λ_. loop loop -- other branch
(λf. n (acc f))
(λf x. n (λg h. h (g f)) (λy. x) (λx. x))) -- pred
n) -- dummy argument
(λf. f) -- 1
乘法可能很难发现，但它确实存在。现在，为了测试它，我评估了应用于 3 的术语，即
(λf x. f (f (f x)))λf x. f (f (f (f (f (f x)))))这是我不久前做过的一个
(define fibs
(lambda (idx)
((((lambda (f)
((lambda (x) (x x))
(lambda (y) (f (lambda (a)
(lambda (b) (((y y) a) b)))))))
(lambda (f) (lambda (s)
(lambda (idx)
(if (= idx 0)
((lambda (p)
(p (lambda (h) (lambda (t) h)))) s)
((f (((lambda (p)
(p (lambda (h) (lambda (t) t)))) s)))
(- idx 1)))))))
((((lambda (f)
((lambda (x) (x x))
(lambda (y) (f (lambda (a)
(lambda (b) (((y y) a) b)))))))
(lambda (f)
(lambda (a)
(lambda (b)
(((lambda (h)
(lambda (t) (lambda (a) ((a h) t)))) a)
(lambda () ((f b) (+ a b)))))))) 0) 1))
idx)))
它定义了所有斐波那契数（当然，通过无限的教堂对列表）
我确实走得更远，去掉了 if、0、1、+ 和 -，但最终无论如何，这些都需要从教堂数字来回转换。 那时它变得很荒谬。
使用标准组合器，用于教堂数字，
FACT = C(C(CI(B(SB)(CB(SB))))(SK))I