Mutually recursive definition of the terms to nonreqursive defenition with Y combinator.

Question

Can't solve this task:

Let there be a mutually recursive definition of the terms ${foo}$ and ${bar}$. In general, it can be written as $$ {foo} = P {foo} {bar} $$ $$ {bar} = Q {foo} {bar} $$ Here $P$ and $Q$ are some terms that contain neither ${foo}$ nor ${bar}$. Using the $Y$-combinator, find nonrecursive definitions for ${foo}$ and ${bar}$. Try to find the most "compact" solution, with the smallest number of $Y$-combinators possible

My attempts

1. I tried to explicitly write $foobar = PfoobarQfoobar$, but it didn't work.
2. I tried to start an auxiliary $bar'=\lambda f.Qf(bar'f)$, and through it get a nonrecursive form with $Y$ combinator.
3. I tried to find the dependence by explicitly describing $foo=Pfoobar=PPfoobarbar=...=P...Pfoobar...bar$.

Answer 1

Disclaimer: I have been reading about lambda calculus and combinatory logic only for some months. But I think that I have an idea for this question. If you find any problems, please comment.

$$\begin{align*} \text{foo} &= \text{P foo bar}\\ &=\text{P foo (Q foo bar)}\\ &=\text{P foo (Q foo (Q foo (...)))}\\ &=\text{P foo (Y (Q foo))}\\ &=\text{P foo (S (K Y) Q foo)}\\ &=\text{S P (S (K Y) Q) foo}\\ &=\text{Y (S P (S (K Y) Q))} \end{align*}$$

Similarly we can extract a definition for $\text{bar}$

Answer 2

Mutual recursion can always be merged. If $f,g$ are mutually recursive, then define a third function $h = \lambda x. x f g$. Now you can express $f = h (\lambda p q. p)$ (Exercise: express $g$), and write a recursive equation using $h$ alone.

---

Another way to solve this is to solve for $f$ assuming you already know $g$. This gives you an expression $f = \dots g\dots$. Now substitute this into the equation for $g$ and you get a recursive equation for $g$ alone, which you can solve using Y.