La factorielle Y-Combinator en javascript fonctionne pour les nombres qui ne correspondent pas aux chiffres de l'église.

Question

J'ai réussi à implémenter l'encodage de l'église et Y-Combinator en utilisant la fonction flèche ES6 en javascript. Mais quand j'ai essayé d'évaluer la fonction factoriel,

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) 

I got 'Uncaught RangeError: taille de la pile d'appel maximale dépassée (...)' erreur.

Si je change FactGen,

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

Il fonctionne.

Ce que je veux savoir est la version numérique de l'église. Comment puis-je y parvenir?

Answer 1

Votre problème est que JavaScript n'est pas paresseux évalué. Plus précisément, le isZero "si" évalue tous ses arguments avant de pouvoir vérifier si le premier est zéro.

Nous pouvons résoudre ce problème en utilisant un if avec des fonctions de l'unité:

// 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)))) 
// ^^^^ 

ou d'omettre l'emballage IF et modifier vos encodages booléens directement à

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