javascript - javascript 中的 Y-Combinator 阶乘适用于数字而不适用于教会数字。

Question

我设法在 javascript 中使用 ES6 箭头函数实现了 Church 编码和 Y-Combinator。但是当我尝试计算阶乘函数时，

FALSE = a => b => b 
TRUE = a => b => a 

ZERO = f => z => z
ONE = f => z => f(z)
SIX = f => z => f(f(f(f(f(f(z))))))
isZERO = n => n(x => FALSE)(TRUE)
SUCC = n => f => z => f(n(f)(z))
MULT = n => m => f => z => n(m(f))(z)

PAIR = a => b => z => z(a)(b)
FIRST = p => p(a => b => a)
SECOND = p => p(a => b => b)
ZZ = PAIR(ZERO)(ZERO)
SS = p => PAIR(SECOND(p))(SUCC(SECOND(p)))
PRED = n => FIRST(n(SS)(ZZ))

FactGen = fact => n =>
  isZERO(n)
    (ONE)
    (MULT(n)(fact(PRED(n))))

Y = g => (x => g(y => x(x)(y))) (x => g(y => x(x)(y)))

Y(FactGen)(SIX) (x=>x+1)(0)

我收到“未捕获的范围错误:超出最大调用堆栈大小 (…)”错误。

如果我改变 FactGen，

FactGen = fact => n => n == 0 ? 1 : n * fact(n - 1)
Y(FactGen)(6)
720

它只是工作。

我想知道的是它的教会数字版本。我怎样才能做到这一点？

Answer 1

你的问题是 JavaScript 不是惰性求值的。具体来说，isZero“if”会在检查第一个参数是否为零之前评估其所有参数。

我们可以使用带有单元函数的 if 来解决这个问题:

// type Bool = a -> a -> a
// type Lazy a = () -> a
// IF :: Bool -> Lazy a -> Lazy a -> a
IF = c => a => b => c(a)(b)()

FactGen = fact => n =>
  IF(isZERO(n))
    (()=>ONE)
    (()=>MULT(n)(fact(PRED(n))))
//   ^^^^

或省略 IF 包装器并将 bool 编码直接更改为

// type Bool = Lazy a -> Lazy a -> a
FALSE = a => b => b()
TRUE = a => b => a()