Essayé de tirer le Z combinator et plutôt dérivée d'une autre
-
29-09-2020 - |
Question
Je travaillais pour dériver le Z-Combinator en commençant par la fonction factorielle et finit par dériver un autre point fixe combinator.Qu'ai-je tirer?J'ai fait une erreur subtile?
Voici les étapes que j'ai effectuées (en JavaScript)
1.Déclarer la fonction factorielle
let fact = n =>
n < 2 ? 1 : n * fact(n - 1)
2.Convertir combinator (fermé expression)
let fact = (self, n) =>
n < 2 ? 1 : n * self(n - 1)
3.Fil auto appel
Basée sur la signature fact(?, 7)
, en passant fact
en tant que premier argument semble raisonnable fact(fact,7)
.Fil le paramètre par la queue composez le:
let fact = (self, n) =>
n < 2 ? 1 : n * self(self, n - 1)
L'utilisation est maintenant fact(fact,7)
→ 5040
4.Refactoriser pour le curry de forme
let fact = self =>
n => n < 2 ? 1 : n * self(self)(n - 1)
5.Déplacer l'application locale de la déclaration de
let fact = self => {
let f = n => self(self)(n)
return n => n < 2 ? 1 : n * f(n - 1)
}
6.Convertir laissez déclaration à l'expression lambda
let fact = self =>
(f =>
n => n < 2 ? 1 : n * f(n - 1)
)(
n => self(self)(n)
)
L'utilisation est encore fact(fact)(7)
→ 5040
7.Séparer la factorielle d'expression
let _fact = f => n =>
n < 2 ? 1 : n * f(n - 1)
let fact = self =>
(
_fact
)(
n => self(self)(n)
)
8.Déplacer l'auto-application à partir de l'appelant pour le corps
let _fact =
f => n => n < 2 ? 1 : n * f(n - 1)
let fact = (() => {
let innerFact = self =>
(
_fact
)(
n => self(self)(n)
)
return innerFact(innerFact)
})()
L'utilisation est maintenant fact(7)
→ 5040
9.Convertir laissez déclaration à l'expression lambda
let _fact =
f => n => n < 2 ? 1 : n * f(n - 1)
let fact = (() => {
return (
innerFact => innerFact(innerFact)
)(
self => (_fact)(n => self(self)(n))
)
})()
10.Simplifier l'expression
let _fact =
f => n => n < 2 ? 1 : n * f(n - 1)
let fact =
(innerFact => innerFact(innerFact))
(self => (_fact)(n => self(self)(n)))
Vérification générale.L'utilisation est encore fact(7)
→ 5040
11.Renommer les variables
L'utilisation de innerFact
et self
regarder étrangement similaire.Renommer à la même variable pour découvrir un modèle.Séparer lexicale étendues donc fort à faire:
let _fact =
f => n => n < 2 ? 1 : n * f(n - 1)
let fact =
(u => u(u))
(u => (_fact)(n => u(u)(n)))
12.Résumé _fact
l'utilisation et le renommer fact
Renommer fact
pour setup
et l'abstrait _fact
dans le corps par le remplacement, avec le paramètre f
let _fact =
f => n => n < 2 ? 1 : n * f(n - 1)
let setup = f =>
(u => u(u))
(u => (f)(n => u(u)(n)))
let fact = setup(_fact)
Pas besoin de séparer _fact
déclaration afin en ligne:
let setup = f =>
(u => u(u))
(u => (f)(n => u(u)(n)))
let fact = setup(
f => n => n < 2 ? 1 : n * f(n - 1)
)
13.Renommer setup
Renommer ce à quoi?Ce combinateur est-ce?Selon Wikipédia Le Z combinator est:
let Z = f =>
(u => f(v => u(u)(v)))
(u => f(v => u(u)(v)))
Mais ce que j'ai dérivé est:
let setup = f =>
(u => u(u))
(u => (f)(n => u(u)(n)))
La définition de fact
en termes de semble équivalent dans le comportement.Ai-je fais une erreur?Je n'ai accidentellement redécouvrir un autre bien connu combinator?
La solution
Si je inline (u => (f)(n => u(u)(n)))
en (u => u(u))
J'obtiens:
(u => f(n => u(u)(n)))
(u => f(n => u(u)(n)))
Ce qui est exactement le Z-Combinator.
De wikipedia:
let Z = f =>
(u => f(v => u(u)(v)))
(u => f(v => u(u)(v)))
Mon calcul:
let fix = f =>
(u => f(n => u(u)(n)))
(u => f(n => u(u)(n)))