我试图用Javascript实现Church's encoding of lambda calculus,但是在编写阶乘函数时开始遇到麻烦:

const factorial = n => (iszero(n))(ONE)(multiply(n)(factorial(predecessor(n))));


iszero(n)用作条件,如果n为零,则返回一个函数执行第一个参数,否则返回第二个函数。

在任何值上调用此函数都会导致堆栈溢出。

我试图简化它以找出原因:

//const ifelse = condition => a => b => condition ? a : b;
//const factorial = n => ifelse(n == 0)(1)(n * factorial(n - 1));
const ifelse = function(condition, a, b) {
    if (condition) {
        return a;
    } else {
        return b;
    }
}
const factorial = function(number) {
    return ifelse(number == 0, 1, number * factorial(number - 1));
}


在这里调用阶乘也将导致溢出,尽管如果我们减小ifelse中的factorial函数,它会生成一个功能完善的阶乘函数,不会抛出:

//const factorial = n => (n == 0) ? (1) : (n * factorial(n - 1));
const factorial = function(number) {
    if (number == 0) {
        return 1;
    } else {
        return number * factorial(number - 1);
    }
}


但是我试图在阶乘内使用函数,所以三元条件运算符是不可接受的(请参见注释的箭头符号)。

为什么在任何值上调用factorial函数都会导致堆栈溢出,并且在仅使用函数(无条件)的情况下可以避免这种情况?

编辑:第一段代码的定义:

const TRUE = x => y => x;
const FALSE = x => y => y;

const ZERO = f => x => x;
const ONE = f => x => f(x);

const pair = a => b => f => f(a)(b);

const first = p => p(TRUE);
const second = p => p(FALSE);

const iszero = n => n(x => FALSE)(TRUE);

const successor = n => f => x => f(n(f)(x));
const multiply = n1 => n2 => f => x => n1(n2(f))(x);
const predecessor = n => second(n(p => pair(successor(first(p)))(first(p)))(pair(ZERO)(ZERO)));

最佳答案

您正在堆栈溢出,因为JavaScript不是一种惰性评估语言。例如:

ifelse(false)(console.log("YES"))(console.log("NO"))
// => YES
//    NO


评估两个参数。防止这种情况发生的方法是保持它们作为功能,直到您需要它们为止。

ifelse(false)(() => console.log("YES"))(() => console.log("NO"))()
// => NO


因此,在第二个factorial定义中,无论如何,factorial(n - 1)都会被执行。 ifelse在那里,您可以选择要返回的两个值中的哪个。显然,factorial(0)然后将调用factorial(-1),它将继续向下直到-infinity(受内存限制)。

保持它们未被评估:

factorial = n => ifelse(n == 0)(() => 1)(() => n * factorial(n - 1)())
factorial(1)()
# => 1
factorial(5)()
// => 120


鉴于您没有定义,我无法告诉您第一套仪器有什么问题,但原因可能相同。

编辑:看过这些定义...让我首先添加自己的一个:

const display = n => n(x => x + 1)(0)


n(x => x + 1)(0)是将教堂数字转换为普通数字的便捷技巧,因此我们可以看到正在发生的情况。仅使用调试工具,因此它不应该破坏您正在做的事情。)

我们的检查员在手... predecessor不正确。看到:

display(successor(predecessor(ONE)))
// => TypeError: f(...) is not a function
//        at f (repl:1:33)
//        at x (repl:1:36)


试试看(直接从您的Wikipedia链接):

const predecessor = n => f => x => n(g => h => h(g(f)))(u => x)(u => u)


完成此操作后,您将获得正确的结果:

display(successor(predecessor(ONE)))
// => 1


现在,转向阶乘。应用与上述相同的技巧(将ifelse分支包装到闭包中,以防止过早评估):

const factorial = n => (iszero(n))(() => ONE)(() => multiply(n)(factorial(predecessor(n))()));

const FIVE = successor(successor(successor(successor(ONE))));
display(factorial(FIVE)())
// => 120

关于javascript - 没有条件的Java递归,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/51667631/

10-12 03:26