7
$\begingroup$

I am trying to understand Y combinators. Could you please explain why the following are equivalent

(Y (f ∘ g))   
(f (Y (g ∘ f)))

(Y is a fixed point combination)

$\endgroup$
5
$\begingroup$

It depends on the notion of equivalence you are using.

Suppose we compare these terms according to their denotational semantics, on $\omega$-CPO domains. Denote with $F,G$ the semantics of the terms $f,g$. Thus, $F,G$ are Scott-continuous functions. Then, we have that the semantics of $Y(f \circ g)$ is, according to the Kleene's fixed point theorem

$$ (1) = [\![ Y(f\circ g) ]\!] = \bigsqcup\{ \bot, F(G(\bot)),F(G(F(G(\bot)))),\ldots\} $$ where $\bigsqcup$ denotes the supremum / least upper bound.

Similarly, we get

$$ (2) = [\![ f(Y(g\circ f) ]\!] = F(\bigsqcup\{ \bot, G(F(\bot)),G(F(G(F(\bot)))),\ldots\}) $$

By continuity, we get $$ (2) = \bigsqcup\{ F(\bot), F(G(F(\bot))),F(G(F(G(F(\bot))))),\ldots\} $$

One can then prove that $(1)=(2)$ by observing that any element of any one chain is bounded above by some element of the other chain. Indeed, we have $$ \bot \sqsubseteq F(\bot), F(G(\bot)) \sqsubseteq F(G(F(\bot))), \ldots $$ estabilishing that $(1)\sqsubseteq(2)$. Further, $$ F(\bot) \sqsubseteq F(G(\bot)), F(G(F(\bot))) \sqsubseteq F(G(F(G(\bot)))), \ldots $$ estabilishing that $(2)\sqsubseteq(1)$, concluding the proof.


Much less formally, the term $Y(f \circ g)$ expresses the infinite application $$ f(g(f(g(\ldots)))) $$ and, similarly, $Y(g \circ f)$ expresses $$ g(f(g(f(\ldots)))) $$ It is fairly natural, then, that applying a single $f$ on top of the second one results in the first one. The above domain-theoretic proof provides a formal justification of that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.