94

什么是组合器??

它是“没有自由变量的函数或定义”(如 SO 所定义)?

或者这个怎​​么样:根据约翰休斯在他关于箭头的著名论文中的说法,“组合器是一个从程序片段构建程序片段的函数”,这是有利的,因为“......使用组合器的程序员构造了许多想要的自动编程,而不是手动编写每个细节”。他接着说,map并且filter是这种组合器的两个常见例子。

一些符合第一个定义的组合子:

一些符合第二个定义的组合子:

  • 地图
  • 筛选
  • 折叠/减少(大概)
  • >>=, compose, fmap 中的任何一个?????

我对第一个定义不感兴趣——那些不会帮助我编写一个真正的程序(如果你说服我我错了,+1)。 请帮助我理解第二个定义。我认为 map、filter 和 reduce 很有用:它们让我可以在更高层次上进行编程——更少的错误、更短和更清晰的代码。以下是我关于组合器的一些具体问题:

  1. 还有哪些组合器的示例,例如 map、filter?
  2. 编程语言经常实现哪些组合子?
  3. 组合器如何帮助我设计更好的 API?
  4. 如何设计有效的组合器?
  5. 什么是非函数式语言(比如 Java)中的组合子,或者这些语言用什么来代替组合子?

更新

感谢@CA McCann,我现在对组合子有了更好的理解。但是一个问题对我来说仍然是一个症结:

使用大量组合子编写的函数程序和不使用组合子编写的函数程序有什么区别?

我怀疑答案是重组合器的版本更短、更清晰、更通用,但如果可能的话,我希望能进行更深入的讨论。

我也在寻找fold常见编程语言中复杂组合子(即比 更复杂)的更多示例和解释。

4

1 回答 1

95

我对第一个定义不感兴趣——那些不会帮助我编写一个真正的程序(如果你说服我我错了,+1)。请帮助我理解第二个定义。我认为 map、filter 和 reduce 很有用:它们让我可以在更高层次上进行编程——更少的错误、更短和更清晰的代码。

这两个定义基本上是一回事。第一个基于正式定义,您提供的示例是原始组合器- 可能的最小构建块。它们可以帮助您编写一个真正的程序,因为您可以使用它们构建更复杂的组合器。将 S 和 K 之类的组合子视为假设的“组合计算机”的机器语言。当然,实际的计算机不会那样工作,因此在实践中,您通常会以其他方式在幕后实现更高级别的操作,但概念基础仍然是理解这些更高级别含义的有用工具操作。

您给出的第二个定义更非正式,并且关于使用更复杂的组合子,以高阶函数的形式以各种方式组合其他函数。请注意,如果基本构建块是上面的原始组合器,那么从它们构建的所有东西都是高阶函数和组合器。但是,在存在其他原语的语言中,您可以区分是函数还是非函数,在这种情况下,组合子通常被定义为以一般方式操作其他函数的函数,而不是对任何非函数进行操作。直接发挥作用。

还有哪些组合器的示例,例如 map、filter?

太多了,不一一列举!两者都将描述单个值行为的函数转换为描述整个集合行为的函数。您还可以拥有转换其他函数的函数,例如端到端组合它们,或者拆分和重新组合参数。您可以拥有将单步操作转换为生成或使用集合的递归操作的组合器。或者各种其他的东西,真的。

编程语言经常实现哪些组合子?

这会有很大的不同。完全通用的组合器相对较少——主要是上面提到的原始组合器——所以在大多数情况下,组合器会对正在使用的任何数据结构有一定的了解(即使这些数据结构是由其他组合器构建的),其中在这种情况下,通常会有一些“完全通用”的组合器,然后是某人决定提供的各种特殊形式。在许多荒谬的情况下,map、fold 和展开(适当的通用版本)足以完成几乎所有你可能想要的事情。

组合器如何帮助我设计更好的 API?

正如您所说,通过考虑高级操作以及它们交互的方式,而不是低级细节。

想想“for each”风格的循环在集合上的流行,它可以让你抽象出枚举集合的细节。在大多数情况下,这些只是映射/折叠操作,通过将其设为组合器(而不是内置语法),您可以执行诸如采用两个现有循环并以多种方式直接组合它们的操作——将一个嵌套在另一个循环中,一个接一个地做,依此类推——只需应用一个组合器,而不是杂耍一大堆代码。

如何设计有效的组合器?

首先,考虑一下对于您的程序使用的任何数据,哪些操作是有意义的。然后考虑如何以通用方式有意义地组合这些操作,以及如何将操作分解为更小的部分,然后再连接在一起。最主要的是使用转换操作,而不是直接操作。当你的函数只是以一种不透明的方式完成一些复杂的功能并且只吐出某种预先消化的结果时,你无能为力。将最终结果留给使用组合器的代码——您想要将您从 A 点带到 B 点的东西,而不是期望成为流程开始或结束的东西。

什么是非函数式语言(比如 Java)中的组合子,或者这些语言用什么来代替组合子?

啊哈哈哈。有趣的是你应该问,因为对象首先是真正的高阶事物——它们有一些数据,但它们也携带着一堆操作,很多构成良好 OOP 设计的东西归结为“对象应该通常充当组合器,而不是数据结构”。

所以这里最好的答案可能是,他们使用具有大量 getter 和 setter 方法或公共字段的类,而不是类似组合器的东西,以及主要包括执行一些不透明的预定义操作的逻辑。

于 2011-09-23T20:40:11.313 回答