1. 引言
函数式编程社区的一大亮点是其善于从代码中识别出抽象模式，并将这些模式与数学中定义明确、具备法则的结构对应起来。这些抽象通常用代数结构（Algebraic Structures）和代数定律（Algebraic Laws）来描述。
本文将从函数式编程的角度出发，定义这些术语，然后逐步建立对代数结构的直觉认知 —— 特别是 Monoid 和 Semigroup。但在深入之前，我们先用最直白的语言来定义 Monoid：
✅ Monoid 是一个接受两个参数的函数，并遵循两个定律：结合律（Associativity）和单位元（Identity）
2. 代数结构
代数结构由一组操作和它们作用的集合组成。在像 Scala 这样的函数式语言中：
- 集合 指的是数据类型（Data Types）
- 操作 指的是类型类（Type Classes）
Monoid 和 Semigroup 就是两种典型的代数结构。
核心思想是将行为与数据分离，通过代数结构定义操作，从而描述数据的行为。
在深入 Monoid 和 Semigroup 之前，我们快速回顾一下类型和类型类。
2.1. 类型（Types）
类型是值的集合。例如 Int、Double、String 都是类型。在 Scala 中，类型是静态的，编译时就确定。
函数式编程中的基本数据类型构建块是 乘积类型（Products） 和 和类型（Coproducts），统称为 代数数据类型（ADTs）。
它们是用“与”和“或”来表达数据的惯用方式：
- 一个形状可以是矩形 或 圆形
- 矩形有宽度 和 高度
- 圆形有半径
在 ADT 中：
- “与”类型（如矩形）是 乘积类型
- “或”类型（如形状）是 和类型
在 Scala 中，通常使用 case class 表示乘积类型，使用 sealed trait 表示和类型：
sealed trait Shape
final case class Rectangle(width: Double, height: Double) extends Shape
final case class Circle(radius: Double) extends Shape
val rect: Shape = Rectangle(3.0, 4.0)
val circ: Shape = Circle(1.0)
2.2. 类型类（Type Class）
类型类是一种类型系统构造，用于支持一组重载操作（方法）。它通过定义一组函数或常量名称及其类型来实现。
✅ 例如：Monoid 和 Semigroup 就是典型的类型类。
类型类包含三个重要组成部分：
- 类型类本身
- 特定类型的类型类实例
- 使用类型类的方法
我们先定义 Semigroup 和 Monoid 的类型类：
trait Semigroup[A] {
def op(x: A, y: => A): A
}
trait Monoid[A] extends Semigroup[A] {
def zero: A
}
到此为止，我们已经对类型、类型类、类型类实例有了基本认知。接下来，我们将用这些知识来研究代数数据结构 —— Monoid 和 Semigroup。
3. Monoid
代数结构中的 Semigroup 是一个集合和一个关联的二元运算符，该运算符将集合中的两个元素合并。
✅ Monoid 则是带单位元（Identity）的 Semigroup
我们先用 Scala 来编码这些定义。
二元操作
二元操作是一个接受两个参数并返回结果的函数：
def |+|[A] (left: A, right: A): A
结合律（Associativity）
Monoid 的二元操作必须满足结合律 —— 操作顺序不重要，可以去掉括号：
(x |+| y) |+| z = x |+| (y |+| z)
单位元（Identity）
Monoid 还必须有一个单位元，对二元操作来说就是“啥都不做”的元素：
e |+| x = x |+| e = x
✅ 这就是 Monoid 的全部定义了！
它们在编程中随处可见。理解它们最好的方式是看几个例子：
- 整数在加法或乘法下构成 Monoid
- 列表的拼接
基本上，任何能“合并”并满足 Monoid 法则的结构都可以称为 Monoid。
接下来，我们用这个抽象来做一个 MapReduce 风格的词频统计任务。
4. 使用 Monoid 实现 MapReduce
在这一节，我们将使用 Monoid 来开发一个 MapReduce 函数。
我们首先定义函数签名：
def wordCount(string: String): Map[String, Int] = ???
def mapMonoid[V: Numeric](map1: Map[K, V], map2: Map[K, V]): Map[K, V] = ???
def frequency(wordCounts: Map[String, Int]*)(implicit monoid: Monoid[Map[String, Int]]): Map[String, Int] = ???
4.1. 统计词频
wordCount 是一个词频统计函数，将被分发到多个计算节点上执行。使用不可变的 Map 保证线程安全：
object WordCount {
case class WordCount(word: String, count: Int)
def wordCount(s: String): Map[String, Int] =
s.split("\\s+")
.map(x => WordCount(x, 1))
.groupBy(w => w.word)
.map(x => (x._1 -> x._2.foldLeft(0)((a, c) => c.count + a)))
.toMap
}
4.2. Monoid 实现
接下来，我们为 Map[K, V] 实现一个 Monoid 实例，其中 V 必须是 Numeric 类型：
object MapMonoidInstance {
implicit def mapMonoid[K, V: Numeric]: Monoid[Map[K, V]] =
new Monoid[Map[K, V]] {
override def zero: Map[K, V] = Map()
override def op(l: Map[K, V], r: => Map[K, V]): Map[K, V] =
l.keySet.union(r.keySet)
.map(k => (k -> implicitly[Numeric[V]].plus(
l.getOrElse(k, implicitly[Numeric[V]].zero),
r.getOrElse(k, implicitly[Numeric[V]].zero)))).toMap
}
}
4.3. 使用 Monoid
最后，frequency 函数是 MapReduce 中的 reduce 阶段。它通过 Monoid 实例将多个 Map 合并为一个：
def frequency(wordCounts: Map[String, Int] *)(implicit monoid: Monoid[Map[String, Int]]): Map[String, Int] =
wordCounts.foldLeft(monoid.zero)(monoid.op(_, _))
⚠️ 关键点：由于 Monoid 满足结合律，聚合顺序不影响结果，因此非常适合并发和分布式计算。
5. 总结
本文我们学习了 Monoid 和 Semigroup 这两种代数结构。
我们首先回顾了类型类和类型类实例，然后自定义了 Monoid 和 Semigroup 的类型类。最后，我们用 Monoid 实现了一个线程安全的 MapReduce 程序。
✅ 代码可以在 GitHub 上找到。