如何使用此类签名制作组合器？

Question

我一直试图用这种类型的签名组合一个组合器:

(a -> b -> c) -> (c -> d -> e) -> a -> b -> d -> e

我已经通过Data.Aviary.Birds和我能找到的所有默认编程帮助网站,但无济于事.此外,如果有一个通用的算法来做这些,将非常感激,但不是必要的.

Answer 1

我们的定义将从这样开始:

foo :: (a -> b -> c) -> (c -> d -> e) -> a -> b -> d -> e
foo abc cde a b d = e

现在让我们填写缺失的位.

我们需要一个e; 得到这个的唯一方法是将第二个函数应用于c和d.

e = cde c d

我们已经给了一个d,但我们需要一个c.我们怎么得到一个c？通过将第一个函数应用于a a和a b.

c = abc a b

我们得到了这两个,所以我们完成了.

foo :: (a -> b -> c) -> (c -> d -> e) -> a -> b -> d -> e
foo abc cde a b d = e
  where
    e = cde c d
    c = abc a b

我们可能就此止步 这是一个非常好的定义.

但是如果我们想试着让它变得更简洁,那么让我们从替换定义开始 e

foo abc cde a b d = cde c d
  where
    c = abc a b

然后是 c

foo abc cde a b d = cde (abc a b) d

我们立即看到我们可以减少去除d.

foo abc cde a b = cde (abc a b)

现在这种类型略显笼统. d -> e已经折叠成一个类型变量,因为它实际上可以是任何东西.

foo :: (a -> b -> c) -> (c -> de) -> a -> b -> de

我们现在可以在鸟舍看到我们的组合器实际上是黑鸟,翻转.

blackbird :: (c -> d) -> (a -> b -> c) -> a -> b -> d

foo :: (a -> b -> c) -> (c -> de) -> a -> b -> de
foo = flip blackbird

事实上,如果我们看一下黑鸟的来源,它看起来就像我们写的那样.

-- | B1 combinator - blackbird - specs 'oo'.
blackbird :: (c -> d) -> (a -> b -> c) -> a -> b -> d
blackbird f g x y = f (g x y)

我们可以更加无点吗？我们可能会考虑不加考虑abc

foo abc cde a b = cde (uncurry abc (a, b))

用函数组合重写这个嵌套

foo abc cde a b = (cde . uncurry abc) (a, b)

并再次回头

foo abc cde a b = curry (cde . uncurry abc) a b

现在我们可以砍掉另外两个参数.

foo abc cde = curry (cde . uncurry abc)

我们绝对应该止步于此.但是如果我们现在推翻这些论点呢？

foo = flip $ \cde abc -> curry (cde . uncurry abc)

重写右半边以使其无点

foo = flip $ \cde abc -> (curry . ((cde .) . uncurry)) abc

和eta再次减少

foo = flip $ \cde -> curry . ((cde .) . uncurry)

并采取一个最后荒谬的步骤

foo = flip $ (curry .) . (. uncurry) . (.)

我们现在点了!

Answer 2

有一个非常简单的方法:作弊.让我们首先找出我们想要的功能.为此,我们去了Djinn.输入

f :: (a -> b -> c) -> (c -> d -> e) -> a -> b -> d -> e

它回来了

f a b c d = b (a c d)

尼斯.现在转到pointfree.io.粘贴在Djinn的定义中,它说

f = flip ((.) . (.))

完成.