求Haskell函数f，g使f g=f。G

Question

在学习Haskell时，我遇到了一个挑战，要找到两个函数f和g，比如f g和f . g是等价的(以及总计，所以f = undefined或f = (.) f之类的东西不算在内)。给出的解决方案是，f和g都等于\x -> x . x (或join (.))。

(我注意到这并不是Haskell特有的；它可以用纯粹的组合逻辑表示为“查找f和g以便f g = B f g"，然后给定的解决方案将转换为f = g = W B)。

我理解为什么当我扩展它的时候，给定的解决方案是有效的，但是我不明白如果你还不知道，你怎么会找到它。以下是我能达到的目标：

• f g = f . g (给定)
• f g z = (f . g) z (eta-双方的扩展)
• f g z = f (g z) (简化RHS)

我不知道怎么从那里开始。我下一步要怎么做才能找到解决办法呢？

Answer 1

我发现，通过考虑教会的数字计算，可以找到一系列的解决方案。在教堂编码中，乘法是通过合成教堂数字来执行的，而指数是通过将基应用于指数来实现的。因此，如果f是某个数字x的教堂编码，而g是某个数字y的教堂编码，那么f g = f . g就意味着y^x = x*y。这个方程的任何非负整数解都转化为原问题的解。示例：

• x=1, y=0, f=id, g=const id
• x=1, y=1, f=id, g=id
• x=1, y=2, f=id, g=join (.)
• 自y^1 = y = 1*y for all y以来，f=id为所有教会数字g工作是有意义的。事实确实如此，事实上，正如Rein所指出的，对于所有的g来说，这都是正确的，而且这很容易通过检查来验证。
• x=2, y=0, f=join (.), g=const id
• x=2, y=2, f=join (.), g=join (.)
• x=3, y=0, f=(.) <*> join (.), g=const id
• 既然0^x = 0 = x*0适用于所有正的x，那么g=const id为所有正的教会数字f工作是有意义的。(它不适用于f=const id，丘奇数字0，这是有意义的，因为0^0是一个不确定的形式。)