非递归 lambda 演算阶乘函数

Question

如何使用 lambda 演算在不使用递归的情况下编写阶乘函数？仅表示数学符号而不是任何特定编程语言的实现。

Answer 1

我没说什么我不是那个意思

"without the use of recursion" 你的意思一定是"without a function calling itself by name"

无论如何，让我们写阶乘

fact := λn. zero? n one (mult n (<b>fact</b> (dec n)))

现在，我们并不特别关心本例中的 zero?、mult、dec 甚至 one；你可以自己实现它们——我们只是想删除粗体的、别名的递归，

... <b>fact</b> (dec n)

最简单的方法是将 lambda 应用于自身——满足 U 组合器

U := λf. f f

现在，我们可以将原始表达式包装在 lambda 中，然后应用 U

fact := <b>U (λf.</b> λn. zero? n one (mult n (<b>???</b> (dec n)))<b>)</b>

但是我们用什么来代替 fact ??? – 回想一下 f 是对外部 lambda 本身的引用，因此为了在下一个 "iteration" 中保持相同的情况，我们必须将 f 应用于自身，就像 U 做到了——事实上，你可以把 U 想象成一面镜子，你的函数可以反射回那面镜子以便重复出现；只是这一次，没有使用名字^_^

fact := U (λf. λn. zero? n one (mult n (<b>f f</b> (dec n))))

是的，是的，但更精明的人会注意到您也可以直接在 lambda 内部使用镜像 (U)

fact := U (λf. λn. zero? n one (mult n (<b>U f</b> (dec n))))

没有U展开

我们知道如何扩展内部——我们第一次就是这样写的

fact := U (λf. λn. zero? n one (mult n (<b>f f</b> (dec n))))

现在展开外层U

fact := (λf. λn. zero? n one (mult n (f f (dec n)))) (λf. λn. zero? n one (mult n (f f (dec n))))

有用吗？

所有教堂数字表示为#N

fact := U λf. λn. zero? n #1 (mult n (U f (dec n)))

fact #4

<b>U (λf. λn. zero? n #1 (mult n (U f (dec n)))</b> #4

<b>(λf. f f)</b> (λf. λn. zero? n #1 (mult n (U f (dec n))) #4

<b>(λf. λn. zero? n #1 (mult n (U f (dec n)))</b> (λf. λn. zero? n #1 (mult n (U f (dec n))) #4

(λn. zero? n #1 (mult n (U <b>(λf. λn. zero? n #1 (mult n (U f (dec n)))</b> (dec n))) #4

zero? <b>#4</b> #1 (mult <b>#4</b> (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec <b>#4</b>)))

zero? #4 #1 (mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4)))

// (zero? #4); false; returns second argument
(mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4)))

// which is #4 * ...
(U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4))

// which is ...
(U (λf. λn. zero? n #1 (mult n (U f (dec n))) <b>#3</b>)

// which is equivalent to...
fact #3

// so ...
(mult #4 (fact #3))

// repeating this pattern ...
(mult #4 (mult #3 (fact #2))
(mult #4 (mult #3 (mult #2 (fact #1)))
(mult #4 (mult #3 (mult #2 (mult #1 (fact #0))))
(mult #4 (mult #3 (mult #2 (mult #1 #1))))
(mult #4 (mult #3 (mult #2 #1)))
(mult #4 (mult #3 #2))
(mult #4 #6)
#24

演示在javascript

继续亲眼目睹 U 组合器的强大功能！

const U =
  f => f (f)
  
const fact =
  U (f => n =>
    n === 0 ? 1 : n * U (f) (n - 1))
    
console.log (fact (4)) // 24

再次作为纯 lambda 表达式

console.log (
  (f => n => n === 0 ? 1 : n * f (f) (n - 1))
    (f => n => n === 0 ? 1 : n * f (f) (n - 1))
      (4)
) // 24

互递归

上面的代码片段演示了这个递归过程的一个非常重要的属性：它是 mutually recursive. As you can see, there are actually two (albeit the same) functions driving the recursion; A calls B, B calls A – However in the case of the U combinator, there is only one function that gets applied to itself, so it does in fact enable direct recursion – lambda 确实使用它的参数调用自己，而不是它的名称（lambda 没有可调用的名称）

Y ?

Because I said so

U 组合器有点麻烦，因为它希望用户 "reflect" 该函数以便重复出现——如果我们可以为外部 lambda 提供一个 镜像函数会怎样本身?

U := λf. f f
Y := λg. U (λf. g (U f))

我将再次向您展示相同的定义，但分两行，以便您可以看到 "mirrors" 及其位置

          / g, user's function
         /
        /  / outer reflection
       /  /
<b>Y := λg. U (λf.</b>   ...   <b>)</b>
                <b>g (U f)</b>
                 \
                  \ call g with inner reflection

所以现在，无论何时将 Y 应用于任何 lambda (g)，它的参数都会变成计算 lambda 本身的函数——改变 fact至

fact := <b>Y</b> (λf. λn. zero? n one (mult n (<b>f</b> (dec n))))

扩展 Y

Y := λg. U (λf. g (U f))             // expand inner U
Y := λg. U (λf. g (f f))             // expand outer U
Y := λg. (λf. g (f f)) (λf. g (f f))

这是您在维基百科上看到的定义；刚刚进行了 alpha 重命名

我有一个深刻的发现

从上面的 U 导出 Y，我看到了我以前从未见过的东西 - 一个隐藏的 B

Y := λg. U (λf. g (U f))

B := λf. λg. λx. f (g x)

Y' := λg. U (B g U)

我见过的最美丽的事物之一 – and it works too；并不是说我们应该有任何理由认为它不会...

#lang lazy

(define B (λ (f)
            (λ (g)
              (λ (x)
                (f (g x))))))

(define U (λ (f)
            (f f)))

(define Y (λ (g)
            (U ((B g) U))))

(define fact (Y (λ (f)
                  (λ (n)
                    (if (= n 0)
                        1
                        (* n (f (sub1 n))))))))

(fact 4) ;; 24

哈斯克勒

你见过Y表示为吗？

Y = U . (. U)
  where U f = f f

Answer 2

如果 "without the use of recursion" 你的意思是没有一般递归并且因此，在没有固定点（或自我应用）的情况下，我们可以简单地观察到阶乘函数是原始递归的（即本质上是迭代的），并且通过迭代（由教会提供）提供了一种非常通用和简单的原始递归编码数字）和对。我将讨论非常有启发性的一般情况。设 < M,N > 是对的一些编码，并设 fst 和 snd 是关联的预测。例如，您可以定义

<M,N> = λz. z M N
fst = λp. p (λxy.x)
snd = λp. p (λxy.y)

假设有一个原始的递归定义（没有参数，为了简单起见）

f(0) = a
f(x+1) = h(x,f(x))

其中 a 和 h 已经定义。

大意是利用一个辅助函数f'，其中

                       f'(x) = <x,f(x)>

因此，f'(0) = < 0, a>，并给定对 p = < x,f(x) > = f'(x)，我们构建下一对 < x+1, f(x+1) > 通过计算第一个组件的后继并将 h 应用于这对参数（也就是说，利用我们的对的编码，简单地相当于将延续 h 作为输入传递给对 p)。

总结一下，

next = λp.< succ (fst p), p h>

最后，为了计算 f(n)，我们需要迭代 n 次下一个函数从<0,a>开始，然后取第二个分量：

 f = λn. snd (n next <0,a>)

非递归 lambda 演算阶乘函数

non recursive lambda calculus factorial function

lambda

functional-programming

lambda-calculus