haskell - 如何使用这种类型签名制作组合器？

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; 获得它的唯一方法是将第二个函数应用于 ac和d。

e = cde c d

我们已经得到了 a d，但我们需要 a c。我们如何得到一个c？通过将第一个函数应用于 ana和 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

我们立即看到我们可以通过 eta reduce 删除d.

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

该类型现在稍微更通用了。 d -> e已经折叠成一个类型变量，因为它实际上可以是任何东西。

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

我们现在可以在 aviary 中看到我们的组合器实际上是翻转的黑鸟。

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)

---

我们可以更免点吗？我们可能会考虑 uncurryingabc

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 ((.) . (.))

完毕。