幺半群(Monoid)

定义

幺半群(Monoid)是抽象代数中的结构:一个集合配上满足结合律的二元运算,且存在单位元。例如整数加法(单位元 0)、整数乘法(单位元 1)、字符串拼接(单位元空串)、列表连接(单位元空列表)都构成幺半群。

在编程中

Haskell 以 Monoid 类型类刻画该结构,提供 mempty(单位元)与 mappend/<>(结合运算)。任何幺半群的元素序列都可以用 fold 归约为单个值,而结合律保证归约的分组方式不影响结果。

应用

结合律使归约可以任意切分并行执行:MapReduce 与流式聚合正是利用这一性质把大数据集切块处理再合并。日志合并、计数器、集合并、取最大值等常见聚合都可建模为幺半群,从而复用同一套并行框架。

相关

去掉单位元要求得到半群(Semigroup);为每个元素补充逆元则得到群。幺半群是函数式程序设计中"用代数结构组织代码"思想的典型入口。