幺半群运算


类别: 函子	组件类型: 概念

描述

幺半群运算是一种特殊的二元函数。一个二元函数必须满足三个条件才能成为幺半群运算。首先，它的第一个参数类型和第二个参数类型必须相同，并且它的结果类型必须与其参数类型相同。其次，必须存在一个单位元。第三，运算必须满足结合律。例如，加法和乘法就是幺半群运算。 [1]

细化

二元函数

关联类型

参数类型	幺半群运算的第一个参数和第二个参数的类型，也是幺半群运算返回时返回的类型。

符号

`F`	作为幺半群运算模型的类型
`T`	`F`的参数类型。
`f`	类型为`F`
`x`, `y`, `z`	类型为`T`

定义

类型F作为二元函数模型是结合的，如果F的第一个参数类型、第二个参数类型和结果类型相同，并且对于任何对象f类型为F以及对于任何对象x, y和z类型为F的参数类型,f(x, f(y, z))与f(f(x, y), z). [2]

有效表达式

除了二元函数要求中描述的表达式之外，以下表达式必须有效。

名称	表达式	类型要求	返回类型
函数调用	`f(x, y)`		`T`
单位元	`identity_element(f)` [3]		`T`

表达式语义

名称	表达式	先决条件	语义	后置条件
函数调用	`f(x, y)`	`x`以及`y`在的域中`f`.	调用`f`使用`x`以及`y`作为参数。
单位元	`identity_element(f)`		返回幺半群的单位元。也就是说，返回值是值`id`类型为`T`使得，对于所有的`x`在的域中`f`, `f(x, id)`以及`f(id, x)`都返回`x`.

复杂性保证

不变式

结合律	对于任何`x`, `y`和`z`类型为`T`, `f(x, f(y, z))`以及`f(f(x, y), z)`返回相同的值。 [4]
单位元。	存在一些元素`id`类型为`T`使得，对于所有的`x`类型为`T`, `f(x, id)`以及`f(id, x)`都返回`x`。表达式`identity_element(f)`返回`id`.

模型

plus<int>
multiplies<double>

备注

[1] 幺半群是三种密切相关的代数结构之一。半群是一个集合 S 和一个二元运算 *，具有以下性质：* 对 S 闭合（即，如果 x 和 y 是 S 的元素，那么 x * y 也是 S 的成员）并且 * 满足结合律（即，如果 x、y 和 z 是 S 的元素，那么 x * (y * z) = (x * y) * z）。幺半群是一个具有单位元的半群。也就是说，存在一些元素 id，使得对于 S 中的所有 x，x * id = id * x = x。最后，群是一个具有以下性质的幺半群：每个元素都有逆元素。也就是说，对于 S 中的每个 x，存在一个元素 xi，使得 x * xi = xi * x = id。例如，实数集在乘法下是一个幺半群（单位元是 1），但它不是一个群。它不是一个群，因为 0 没有逆元素。

[2] 数学教科书通常将其写成一个方程，而不是使用“与...相同”之类的词语。但是，我们不能在这个定义中使用相等，因为F的参数类型可能不是可比较相等的。如果F的参数类型是可比较相等的，但是，那么这两个表达式应该相等：结合律的条件变为f(x, f(y, z)) == f(f(x, y), z)

[3] 这是作为重载函数实现的。函数identity_element在标准头文件 functional 和非标准向后兼容头文件 function.h 中定义，用于类型为plus<T>以及multiplies<T>的参数。如果您定义了一个新的幺半群运算F（例如，矩阵乘法），您必须重载identity_element用于类型为F的参数。该identity_element函数是 SGI 扩展；它不是 C++ 标准的一部分。

[4] 结合律与交换律不同。也就是说，要求x * (y * z) == (x * y) * z与要求x * y == y * x完全无关。幺半群运算需要满足结合律，但不需要满足交换律。例如，矩阵在乘法下形成幺半群，即使矩阵乘法不满足交换律。

另请参阅

二元函数, plus, multiplies