找到Haskell函数f,g使得fg = f.G

Question

虽然学习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 (双方的扩张)
• 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对所有人而言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是一种不确定的形式.)