第13章：幺半群统合万物

广义组合

本章将通过半群（Semigroup）视角来剖析幺半群（Monoid）。幺半群是数学抽象中的粘合剂，其概念跨越多个学科领域，如量子纠缠般统合计算本质。它们是统御计算的原始动力，是代码库的氧气，是程序运行的基石，是抽象逻辑的内禀连接。

幺半群的核心在于组合。何为组合？它可以是累积、连接、乘法、选择，甚至求值运算！本章将展示多个示例，但我们仅初探其冰山一角。幺半群实例丰富且应用广泛，目的是建立深层直觉以构造自定义幺半群。

抽象的加法运算

通过抽象视角观察，加法运算存在若干有趣特性。

首先，这是二元操作：同一集合内，输入两个元素返回一个新元素。

// a binary operation
1 + 1 = 2

定义域内两个数值，上域生成单一结果且保持数集封闭性。这意味着无论输入何值，类型始终不变，因此可链式调用：

// we can run this on any amount of numbers
1 + 7 + 5 + 4 + ...

此外（精心设计的双关语...），加法满足结合律，这让我们可以按需分组运算。技术角度说，这种结合性的二元操作天然适合并行计算，因为任务可分块分发。

// associativity
(1 + 2) + 3 = 6
1 + (2 + 3) = 6

需注意这不等于交换律——交换律允许操作数重排序。虽然加法满足交换性，但目前暂不关注此类特性，因其过于具体违背抽象宗旨。

进一步思考：抽象超类应包含哪些属性？哪些特性是加法独有的？又是哪些可泛化的？存在层级式抽象吗？这恰是数学先驱构思抽象代数时的思维方式。

历史发展轨迹显示，早期抽象代数通过'群（Group）'来泛化加法。群概念包含逆元等完整特性，而此处仅关注结合律二元操作，这是选择'半群（Semigroup）'接口的主要原因。半群类型拥有concat方法，代表可结合二元操作符。

现为加法实现Sum类型：

const Sum = x => ({
  x,
  concat: other => Sum(x + other.x)
})

注意concat方法始终返回新Sum实例。

此处使用对象工厂而非原型模式，原因在于Sum非pointed且避免new语法。实际应用示例如下：

Sum(1).concat(Sum(3)) // Sum(4)
Sum(4).concat(Sum(37)) // Sum(41)

通过接口编程而非具体实现，这得益于建立在群论上的接口，可复用数百年的数学研究成果。

如前所述，Sum既非pointed也非函子。验证定律可知：因其仅限于数值类型，map在此不适用——无法转换为其他类型。

用途何在？通过替换实例获得多样结果：

const Product = x => ({ x, concat: other => Product(x * other.x) })

const Min = x => ({ x, concat: other => Min(x < other.x ? x : other.x) })

const Max = x => ({ x, concat: other => Max(x > other.x ? x : other.x) })

该模式不限于数值，其他类型示例如下：

const Any = x => ({ x, concat: other => Any(x || other.x) })
const All = x => ({ x, concat: other => All(x && other.x) })

Any(false).concat(Any(true)) // Any(true)
Any(false).concat(Any(false)) // Any(false)

All(false).concat(All(true)) // All(false)
All(true).concat(All(true)) // All(true)

[1,2].concat([3,4]) // [1,2,3,4]

"miracle grow".concat("n") // miracle grown"

Map({day: 'night'}).concat(Map({white: 'nikes'})) // Map({day: 'night', white: 'nikes'})

长时凝视这些范例后，模式将如魔眼三维画般突然显现：合并数据结构、组合逻辑运算、构建字符串等，几乎所有任务皆可归约至此组合接口。

文中多次使用的Map实为Object包装器，通过添加方法扩展功能，不影响原有结构。

所有常用函子皆为半群。

观察Identity类型（原名为Container）：

Identity.prototype.concat = function(other) {
  return new Identity(this.__value.concat(other.__value))
}

Identity.of(Sum(4)).concat(Identity.of(Sum(1))) // Identity(Sum(5))
Identity.of(4).concat(Identity.of(1)) // TypeError: this.__value.concat is not a function

当且仅当其内部值为半群时，该组合类型自身成为半群。犹如笨拙的高空滑翔翼，承载半群便拥有半群特性。

其他类型类似：

// combine with error handling
Right(Sum(2)).concat(Right(Sum(3))) // Right(Sum(5))
Right(Sum(2)).concat(Left('some error')) // Left('some error')


// combine async
Task.of([1,2]).concat(Task.of([3,4])) // Task([1,2,3,4])

嵌套半群结构展现强大能力：

// formValues :: Selector -> IO (Map String String)
// validate :: Map String String -> Either Error (Map String String)

formValues('#signup').map(validate).concat(formValues('#terms').map(validate)) // IO(Right(Map({username: 'andre3000', accepted: true})))
formValues('#signup').map(validate).concat(formValues('#terms').map(validate)) // IO(Left('one must accept our totalitarian agreement'))

serverA.get('/friends').concat(serverB.get('/friends')) // Task([friend1, friend2])

// loadSetting :: String -> Task Error (Maybe (Map String Boolean))
loadSetting('email').concat(loadSetting('general')) // Task(Maybe(Map({backgroundColor: true, autoSave: false})))

首例组合了包含Either和Map的IO来验证合并表单值；次例使用Task和Array异步合并多服务器结果；末例堆叠Task、Maybe和Map实现加载、解析及合并配置。

尽管可用chain或ap实现，但半群能以更简洁方式表达意图。

这特性超越函子范畴。事实上，任何由半群构成的结构本身也是半群——组件可组合则整体可组合。

const Analytics = (clicks, path, idleTime) => ({
  clicks,
  path,
  idleTime,
  concat: other =>
    Analytics(clicks.concat(other.clicks), path.concat(other.path), idleTime.concat(other.idleTime))
})

Analytics(Sum(2), ['/home', '/about'], Right(Max(2000))).concat(Analytics(Sum(1), ['/contact'], Right(Max(1000))))
// Analytics(Sum(3), ['/home', '/about', '/contact'], Right(Max(2000)))

可见各元素皆具自组合能力。使用Map类型即可自由组合：

Map({clicks: Sum(2), path: ['/home', '/about'], idleTime: Right(Max(2000))}).concat(Map({clicks: Sum(1), path: ['/contact'], idleTime: Right(Max(1000))}))
// Map({clicks: Sum(3), path: ['/home', '/about', '/contact'], idleTime: Right(Max(2000))})

可无限堆叠组合结构。如同林间添木或野火蔓延，取决于代码实际情况。

默认做法是组合容器内容，但存在直接组合容器的情况，例如Stream类型：

const submitStream = Stream.fromEvent('click', $('#submit'))
const enterStream = filter(x => x.key === 'Enter', Stream.fromEvent('keydown', $('#myForm')))

submitStream.concat(enterStream).map(submitForm) // Stream()

事件流可通过合并生成新流，或要求内容为半群进行组合。对于Task，可依时间顺序选择结果或优先取Right值。Alternative接口实现这些选择性组合策略，建议按需研究。

空值幺半群

在抽象加法时，我们如同古巴比伦人般缺失零的概念（文中零被忽略）。

零元素作为单位元（Identity），满足$a + 0 = a = 0 + a$。抽象视角下，可视作中性的*空（empty）*元素。现代码实现之：

// identity
1 + 0 = 1
0 + 1 = 1

称此概念为empty并定义新接口，延续简短命名传统：Monoid（幺半群）。构造方式为半群附加单位元，类型通过empty方法实现：

Array.empty = () => []
String.empty = () => ""
Sum.empty = () => Sum(0)
Product.empty = () => Product(1)
Min.empty = () => Min(Infinity)
Max.empty = () => Max(-Infinity)
All.empty = () => All(true)
Any.empty = () => Any(false)

空值有何用处？犹如询问零为何重要——答案不言自明。

零缺陷是我们的追求，零风险是代码的准则。当海啸来袭时，它既是诺亚方舟也是灭世洪水。全新开端，亦是终极致命价签：既可摧枯拉朽，亦能绝处逢生。

代码层面的合理默认值：

const settings = (prefix="", overrides=[], total=0) => ...

const settings = (prefix=String.empty(), overrides=Array.empty(), total=Sum.empty()) => ...

或在空数据时返回有效值：

sum([]) // 0

同时也是聚合的理想初始值……

折叠世界

concat和empty完美契合reduce首两位参数。使用reduce聚合半群数组时忽略empty会导致潜在风险：

// concat :: Semigroup s => s -> s -> s
const concat = x => y => x.concat(y)

[Sum(1), Sum(2)].reduce(concat) // Sum(3)

[].reduce(concat) // TypeError: Reduce of empty array with no initial value

空数组触发异常。JavaScript虽不阻拦我们绑着运动鞋开枪，但在空数组时直接死锁程序。若继续执行需要正确类型的结果，返回Maybe虽可表失败，我们有更好方案。

通过柯里化改造reduce，创建强制传入empty的fold函数保障安全：

// fold :: Monoid m => m -> [m] -> m
const fold = reduce(concat)

用empty值作为初始m，将m类型的数组熔炼为单一结晶。

fold(Sum.empty(), [Sum(1), Sum(2)]) // Sum(3)
fold(Sum.empty(), []) // Sum(0)

fold(Any.empty(), [Any(false), Any(true)]) // Any(true)
fold(Any.empty(), []) // Any(false)


fold(Either.of(Max.empty()), [Right(Max(3)), Right(Max(21)), Right(Max(11))]) // Right(Max(21))
fold(Either.of(Max.empty()), [Right(Max(3)), Left('error retrieving value'), Right(Max(11))]) // Left('error retrieving value')

fold(IO.of([]), ['.link', 'a'].map($)) // IO([<a>, <button class="link"/>, <a>])

后两例手动传入empty值，因类型无法自提供。静态类型语言可自动推断，但此处需显式传参。

非完全幺半群

部分半群无法定义单位元，如First类型：

const First = x => ({ x, concat: other => First(x) })

Map({id: First(123), isPaid: Any(true), points: Sum(13)}).concat(Map({id: First(2242), isPaid: Any(false), points: Sum(1)}))
// Map({id: First(123), isPaid: Any(true), points: Sum(14)})

合并账户时保留首个ID，此类半群无合法empty值，但仍有实用价值。

大一统理论

群论或范畴论？

二元操作在抽象代数中无处不在，是*范畴（Category）*的基础操作。但无单位元则无法建立范畴模型，因此我们基于半群引入单位元后，转至范畴论的幺半群结构。

幺半群构成单对象范畴：态射为concat，单位元为empty，组合性得证。

作为幺半群的函数组合

满足a -> a类型的自同态（Endomorphism）可构成Endo幺半群：

const Endo = run => ({
  run,
  concat: other =>
    Endo(compose(run, other.run))
})

Endo.empty = () => Endo(identity)


// in action

// thingDownFlipAndReverse :: Endo [String] -> [String]
const thingDownFlipAndReverse = fold(Endo(() => []), [Endo(reverse), Endo(sort), Endo(append('thing down')])

thingDownFlipAndReverse.run(['let me work it', 'is it worth it?'])
// ['thing down', 'let me work it', 'is it worth it?']

通过函数组合实现concat，保持类型自洽。

作为幺半群的Monad（单子）

join操作以结合性方式压平嵌套Monad（单子），也是自然变换。限定*自函子（Endofunctor）*范畴时，join即形成该范畴的幺半群——即Monad。具体代码实现建议查阅资料，此为核心理念。

作为幺半群的Applicative

应用函子对应松弛幺半函子，可通过幺半群实现并推导ap方法：

// concat :: f a -> f b -> f [a, b]
// empty :: () -> f ()

// ap :: Functor f => f (a -> b) -> f a -> f b
const ap = compose(map(([f, x]) => f(x)), concat)

总结

万物相连皆可建模。幺半群作为强力抽象工具，既可描述宏观架构亦可雕琢微观数据。建议在涉及累积与组合场景时优先考虑幺半群，触类旁通扩展应用边界——其建模能力常超乎想象。

练习