7

在学习 Haskell 时，我遇到了一个挑战，要找到两个函数f和g，这样f g和f . g是等价的（和总数，所以喜欢f = undefined或f = (.) f不计算）。给定的解决方案是f和g都等于\x -> x . x（或join (.)）。

（我注意到这不是 Haskell 特有的；它可以用纯组合逻辑表示为“find fand gsuch that 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）

而且我不知道如何从那里开始。在尝试找到解决方案时，我接下来会做什么？

4

1 回答 1

9

我发现通过考虑 Church 数字计算可以找到一系列解决方案。在 Church 编码中，乘法是通过组合 Church 数字来执行的，而乘方是通过将基数应用于指数来执行的。因此，如果f是某个数字的 Church 编码x，并且g是某个数字的 Church 编码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对于所有人来说，适用于所有 Church 数字都是y有意义的。确实如此，事实上，正如 Rein Henrichs 所指出的，这对所有人都是正确的，这很容易通过检查来验证。f=idgg
  • 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所有正数 Church 数字都有效f。（它不适用于f=const id，教会数字 0，这是有道理的，因为0^0它是一种不确定的形式。）
于 2019-01-26T05:51:25.820 回答