函数式设计中的常见结构：幺半群深入解析

### 函数式设计中的常见结构：幺半群深入解析 #### 1. 函数式设计新视角 在函数式设计的领域中，我们已经基于相关原则编写了许多库。此前，我们将这些原则应用到了一些具体的问题领域。现在，我们要从更广泛的视角出发，探究函数式编程中出现的常见模式。这种抽象不仅能消除重复代码，将抽象概念以类、接口和函数的形式呈现，应用于实际程序，更重要的是实现概念整合。当我们识别出不同上下文中不同解决方案的共同结构时，就能用一个定义统一这些结构实例并为之命名。而且，如果其他人也使用相同的词汇，我们就能高效地交流设计思路。 #### 2. 幺半群的引入 我们选择从幺半群开始，因为它简单、普遍且实用。在日常编程中，无论是否意识到，幺半群无处不在。处理列表、拼接字符串以及累加循环结果等操作，常常可以用幺半群来表述。幺半群的作用主要体现在两个方面：一是便于并行计算，可将问题分解为多个能并行计算的小块；二是可以组合简单计算来完成复杂计算。 ##### 2.1 什么是幺半群 让我们先看字符串拼接的代数性质。例如，"foo" + "bar" 得到 "foobar"，空字符串是该操作的单位元，即 (s + "") 或 ("" + s) 的结果总是 s。并且，拼接三个字符串 (r + s + t) 时，操作满足结合律，无论如何加括号，((r + s) + t) 或 (r + (s + t)) 的结果都相同。 整数加法也遵循相同规则，(x + y) + z 总是等于 x + (y + z)，单位元是 0。乘法的单位元是 1，布尔运算符 && 和 || 同样满足结合律，单位元分别是 true 和 false。 这种代数结构被称为幺半群，结合律和单位元定律统称为幺半群定律。幺半群由以下部分组成： - 某种类型 A - 一个结合性的二元操作 combine，它接受两个类型 A 的值并将它们组合成一个：对于任意的 x: A, y: A, z: A，有 combine(combine(x, y), z) == combine(x, combine(y, z)) - 一个值 empty: A，它是该操作的单位元：对于任意的 x: A，有 combine(x, empty) == x 且 combine(empty, x) == x 在 Scala 中，可以用如下特质表示： ```scala trait Monoid[A]: def combine(a1: A, a2: A): A def empty: A ``` 以下是字符串幺半群的示例： ```scala val stringMonoid: Monoid[String] = new: def combine(a1: String, a2: String) = a1 + a2 val empty = "" ``` 列表拼接也构成幺半群： ```scala def listMonoid[A]: Monoid[List[A]] = new: def combine(a1: List[A], a2: List[A]) = a1 ++ a2 val empty = Nil ``` 同时，还有一些相关练习： - **练习 10.1**：给出整数加法、乘法以及布尔运算符的幺半群实例。 ```scala val intAddition: Monoid[Int] val intMultiplication: Monoid[Int] val booleanOr: Monoid[Boolean] val booleanAnd: Monoid[Boolean] ``` - **练习 10.2**：给出组合 Option 值的幺半群实例。 ```scala def optionMonoid[A]: Monoid[Option[A]] ``` - **练习 10.3**：为自同态函数编写幺半群。 ```scala def endoMonoid[A]: Monoid[A => A] ``` - **练习 10.4**：使用之前开发的基于属性的测试框架实现幺半群定律的属性，并测试已编写的幺半群。 ```scala def monoidLaws[A](m: Monoid[A], gen: Gen[A]): Prop ``` 需要注意的是，除了满足幺半群定律外，各种幺半群实例之间可能没有太多关联。幺半群就是一种类型，加上幺半群操作和一组定律，仅此而已。 #### 3. 用幺半群折叠列表 幺半群与列表有着紧密联系。观察列表的 foldLeft 和 foldRight 方法的签名，当 A 和 B 是相同类型时： ```scala def foldRight(acc: A)(f: (A, A) => A): A def foldLeft(acc: A)(f: (A, A) => A): A ``` 幺半群的组件与这些参数类型完美匹配。例如，对于字符串列表，我们可以传递字符串幺半群的 combine 和 empty 函数来折叠列表并拼接所有字符串： ```scala scala> val words = List("Hic", "Est", "Index") words: List[String] = List(Hic, Est, Index) scala> val s = words.foldRight(stringMonoid.empty)(stringMonoid.combine) s: String = "HicEstIndex" scala> val t = words.foldLeft(stringMonoid.empty)(stringMonoid.combine) t: String = "HicEstIndex" ``` 这里存在一个术语上的小差异，程序员和数学家在谈论一个类型是幺半群还是有幺半群实例时有所不同。准确地说，类型 A 在 Monoid[A] 实例定义的操作下构成幺半群，不太精确地说，我们可以说类型 A 是幺半群或具有幺半群性。Monoid[A] 实例只是这一事实的证明。 #### 4. 结合律与并行性 使用幺半群折叠列表时，选择 foldLeft 还是 foldRight 并不重要，因为结合律和单位元定律保证了结果相同。左折叠将操作向左关联，右折叠将操作向右关联，单位元分别在左侧和右侧。 我们可以编写一个通用函数 combineAll 来用幺半群折叠列表： ```scala def combineAll[A](as: List[A], m: Monoid[A]): A ```