haskell - 找到 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 的 Church 编码，和g是某个数字 y 的 Church 编码，然后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对于所有人y ，这是有道理的 f=id适用于所有教堂数字 g 。情况确实如此，事实上，正如 Rein Henrichs 指出的那样，这对所有人来说都是如此 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 是一种不确定的形式。)