找到Haskell函数f和g，使得f g = f . g。

Question

找到Haskell函数f和g，使得f g = f . g。

haskellfunctional-programminglambda-calculuscombinatory-logic

7

在学习Haskell的时候，我遇到了一个挑战，要找到两个函数f和g，使得f g和f . g是等价的（并且是total的，因此像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)（简化右侧）

接下来我不知道该怎么做。在尝试找到解决方案时，我该怎么做？

- Joseph Sible-Reinstate Monica

2

也许开始的地方是弄清楚它们必须具有哪些类型。事实证明，为了使表达式有意义，它们必须具有多态类型，这可以告诉您可能的实现方式。 - luqui

4

设 f 为恒等函数，g 为任意函数。则有 id g = g = id . g。 - Rein Henrichs

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joseph Sible-Reinstate Monica · Accepted Answer

我发现通过考虑Church数计算可以找到一组解。在Church编码中，通过组合Church数进行乘法运算，在底数上应用指数进行指数运算。因此，如果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，y^1 = y = 1*y，所以f=id适用于所有的Church数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
由于对于所有正数的x，0^x = 0 = x*0，因此g=const id适用于所有正Church数f。（它不适用于f=const id，Church数0，这是有道理的，因为0^0是一个不定形式。）