While learning Haskell, I came across a challenge to find two functions f and g, such that f g and f . g are equivalent (and total, so things like f = undefined or f = (.) f don't count). The given solution is that f and g are both equal to \x -> x . x (or join (.)).
(I note that this isn't Haskell-specific; it can be expressed in pure combinatory logic as "find f and g such that f g = B f g", and the given solution would then translate to f = g = W B.)
I understand why the given solution works when I expand it out, but I don't understand how you'd ever find it if you didn't already know it. Here's how far I can get:
f g = f . g (given)f g z = (f . g) z (eta-expansion of both sides)f g z = f (g z) (simplify the RHS)And I don't know how to proceed from there. What would I do next in trying to find a solution?
I discovered that it's possible to find a family of solutions by considering Church numeral calculation. In the Church encoding, multiplication is performed by composing the Church numerals, and exponentiation is performed by applying the base to the exponent. Thus, if f is the Church encoding of some number x, and g is the Church encoding of some number y, then f g = f . g implies y^x = x*y. Any nonnegative integer solutions to this equation translate to solutions to the original problem. Examples:
x=1, y=0, f=id, g=const idx=1, y=1, f=id, g=idx=1, y=2, f=id, g=join (.)y^1 = y = 1*y for all y, it makes sense that f=id works for all Church numerals g. This is indeed the case, and in fact, as Rein Henrichs pointed out, it's true for all g, and this is easily verifiable by inspection.x=2, y=0, f=join (.), g=const idx=2, y=2, f=join (.), g=join (.)x=3, y=0, f=(.) <*> join (.), g=const id0^x = 0 = x*0 for all positive x, it makes sense that g=const id works for all positive Church numerals f. (It does not work for f=const id, Church numeral 0, which makes sense since 0^0 is an indeterminate form.)