幺半群

幺半群刻画“可结合地连续组合，并有一个什么都不做的操作”：结合律保证长串组合无需记录括号，单位元则代表空过程。它足以表达重复合成和空合成，却不要求每个元素都能撤销，因此比群更适合描述字符串拼接、状态转换和带损失的计算。

自然数在加法下以 $0$ 为单位元，是交换幺半群但不是群；若底层集合只取正整数，加法半群便没有单位元。字符串在拼接下以空字为单位元，通常不交换。所有从集合 $X$ 到自身的函数在复合下形成幺半群，非双射函数没有逆。每个群都是幺半群，但自然数加法幺半群中除 $0$ 外没有加法逆元；这说明成为幺半群并不要求普遍可逆。空集合在某些二元运算下无法拥有单位元，因此不能只检查结合律。

幺半群是自由幺半群、矩阵乘法、函数复合以及程序状态变换的共同抽象。幺半群作用公理库幺半群作用Monoid action · Act of a monoid · M-set把可组合但未必可逆的操作一致地作用到对象集合上。进一步说明这些可组合操作怎样一致地作用到状态或摘要上。幺半群同态保持运算与单位元，使复杂对象可通过可组合摘要进行折叠和并行归约。半群公理库半群Semigroup带有结合二元运算的集合。加入单位元成为幺半群，再要求可逆得到 群公理库群Group配备结合二元运算、单位元，并且每个元素都有逆元的集合。。自由幺半群公理库自由幺半群Free monoid由给定字母集合上的有限串及连接运算组成、满足相应泛性质的幺半群。承载形式语言；有限幺半群识别正则语言，算法中的区间聚合和并行归约则利用其结合律与单位元。

这一接口让同一摘要跨结构复用：搜索树增强公理库搜索树增强定理与方法Search-tree augmentation在搜索树节点维护可由局部子树摘要恢复的信息，并证明旋转后仍可常数更新。把左右子树摘要结合，并行 scan公理库并行前缀扫描parallel prefix scan · parallel scan · prefix computation用上扫归约和下扫传播在线性工作、对数深度内计算任意幺半群运算的全部前缀。沿 computation DAG 组合前缀，可合并摘要公理库可合并摘要mergeable summary · mergeable sketch让分片流的有限状态在不读取原始数据时组合，并保持与集中处理相容的统计保证。把分片结果合成整体。结合律允许重新括号化，但没有逆元时不能靠“相减”删除任意贡献，动态更新仍需具体结构。