1

我设法在 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)

我收到“未捕获 RangeError：超出最大调用堆栈大小（…）”错误。

如果我改变 FactGen，

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

它只是工作。

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

4

1 回答 1

3

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

我们可以使用ifwith 单位函数来解决这个问题：

// 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()
于 2015-10-28T10:07:51.597 回答