javascript中的Y-Combinator阶乘对数字有效，而不是对教会数字有效。

Question

我设法使用javascript中的ES6箭头函数实现了教会编码和Y-组合器。但是当我尝试计算阶乘函数时，

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)

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

如果我改变了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包装器，将布尔编码直接更改为

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