仅具有 lambda 表达式的阶乘函数

Question

您可以仅使用 lambda 表达式自行创建的最透明、最优雅的阶乘函数是什么？

我的一个学生在伯克利参加了一个计划课程，并获得了仅使用 lambda 表达式（没有定义、let 或其他幂过程）创建阶乘函数的额外学分问题。我花了一段时间才解决，而且很复杂而且很难看。

几年后，我现在正在教授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 (!) (! !))
    (lambda (!)
      (lambda (n acc)
        (if (zero? n)
            acc
            ((! !) (sub1 n) (* n acc))))))
   n 1))

很难在更少的空间中获得递归。自应用程序必须发生在某个地方，并且大多数按值调用语言（如Scheme）中的独立固定点都必须引入额外的 lambda 以避免自应用程序中的失控递归。

相反，我的解决方案和 Jeremiah 的解决方案将自我应用程序隐藏在Scheme 的短路 if 的一个分支中，从而以少得多的字符提供必要的递归。

Answer 3

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

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

Answer 4

这是我之前在研究 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)]

Answer 5

我首先在无类型 lambda 演算中编写解决方案，使用诸如 0？、true、false 等的顶级定义，定义使用教会编码。此实现假设多参数函数是柯里化的并且函数是部分应用的（如 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)))

Church 布尔值 true 和 false 定义如下

(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 (fx)))。混合应用和混合正态评估都减少到正常项而不发散，产生λf x。 f (f (f (f (f (fx)))))，或 6。其他归约策略要么发散（由于自我应用），要么不归约到正常形式。

Answer 6

这是我不久前做的一个

 (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、+ 和 -，但在无论如何，这些都需要从教堂数字来回转换。那时它变得很荒谬。