代码之家 › 专栏 › 技术社区 › Joseph Sible-Reinstate Monica

查找haskell函数f,g,使f g=f。G

combinatory-logic lambda-calculus functional-programming haskell

7

Joseph Sible-Reinstate Monica · 技术社区 · 6 年前

在学习haskell时,我遇到了一个难题,要找到两个函数 f 和 g ,这样 f g 和 f . g 是相等的(和总数,所以 f = undefined 或 f = (.) f 不要数数。给定的解决方案是 f 和 G 都等于 \x -> x . x (或) join (.) )

(我注意到这不是特定于haskell的;它可以用纯组合逻辑表示为“find” 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)

我不知道如何从那里开始。接下来我该怎么做才能找到解决方案呢?

1 回复 | 直到 6 年前

1

8

Joseph Sible-Reinstate Monica 6 年前

我发现通过考虑教堂的数字计算,有可能找到一系列的解决方案。在教堂编码中,乘法是通过组合教堂数字来实现的,而求幂是通过将基数应用于指数来实现的。因此,如果 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 为了所有 Y 有道理的是 f=id 适用于所有教堂数字 G . 这确实是事实,而且事实上,正如雷恩·亨里克斯指出的那样,这对所有人都是正确的。 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 是不确定的形式。)