Y-Combinator factorial в javascript работает для чисел не для церковных цифр.

Question

Мне удалось реализовать кодовое кодирование и Y-Combinator, используя функцию со стрелкой ES6 в javascript. Но когда я попытался оценить функцию факториала,

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()