编程中的幺半群/半群的例子

Question

众所周知,幺半群在编程中无处不在.它们无处不在,非常有用,作为一个"爱好项目",我正在开发一个完全基于其属性的系统(分布式数据聚合).为了使系统有用,我需要有用的monoids :)

我已经知道了这些:

• 数字或矩阵和
• 数字或矩阵产品
• 具有顶部或底部元素的总订单下的最小值或最大值(更一般地,在有界点阵中加入或满足,或者更一般地,在类别中的产品或副产品)
• 设置联盟
• 使用monoid连接冲突值的映射联合
• 有限集子集的交集(如果我们谈论半群,则只是设置交集)
• 地图与有界关键域的交叉(在此处相同)
• 合并序列的合并,可能在不同的幺半群/半群中加入键相等的值
• 排序列表的有界合并(与上面相同,但我们取结果的前N个)
• 两个幺半群或半群的笛卡尔积
• 列出连接
• Endomorphism组成.

现在,让我们将操作的准属性定义为保持等价关系的属性.例如,如果我们考虑相等长度或相同内容直到排列的列表是等效的,则列表串联是准可交换的.

这里有一些准幺半群和准交换幺半群和半群:

• 任何(a + b = a或b,如果我们认为载体的所有元素都是等价的)
• 任何令人满意的谓词(a + b = a和b中的一个非空并且满足某个谓词P,如果没有则为null;如果我们认为所有元素都满足P等价)
• 随机样本的有界混合(xs + ys =来自xs和ys串联的大小为N的随机样本;如果我们考虑与整个数据集具有相同分布的任何两个样本相等)
• 加权随机样本的有界混合
• 我们称之为"拓扑合并":给出两个非循环和非矛盾的依赖图,一个包含两者中指定的所有依赖关系的图.例如,列出可以产生任何排列的"连接",其中每个列表的元素按顺序跟随(例如,123 + 456 = 142356).

其他哪些确实存在？

Answer 1

商幺星是另一种形成幺半群的方式(quasimonoids？):给定monoid M和等价关系〜与乘法兼容,它给出了另一个幺半群.例如:

• 带有并集的有限多重集:如果A*是一个自由的monoid(带连接的列表),〜是"是"关系的排列,那么A*/〜是一个自由的可交换的monoid.

• 带有union的有限集:如果〜被修改为忽略元素的数量(所以"aa"〜"a")那么A*/〜是一个自由的可交换幂等幺半群.

• 句法幺半群:任何常规语言都会产生句法幺半群,它是A*与"语言不可区分"关系的商.这是一个手指树实现这个想法.例如,语言{a ³ⁿ:n natural}具有Z ₃作为句法幺半群.

商数幺半群自动带有同态M - > M /〜,这是完全的.

"双重"构造是子类.它们具有同态A - > M是单射的.

幺半群的另一种结构是张量积.

Monoids允许通过在O(log n)和快速并行前缀和计算中求平方来进行指数化.它们也用在Writer monad中.

Answer 2

Haskell标准库因其类型类的实际数学术语的使用而被交替称赞和攻击.(在我看来,这是一件好事,因为没有它,我甚至都不知道幺半群是什么!).在任何情况下,您可以查看http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Monoid.html以获取更多示例:

• 任何幺半群的对偶是一个幺半群:给定a + b,用++ b = b + a定义一个新的操作++
• 布尔的结合和分离
• 在Maybe monad(也就是Ocaml中的"选项")中,第一个也是最后一个.那是,

  first (Just a) b = Just a
  first Nothing b = b

  同样也是最后的

后者只是与monad和箭头相关的一整个幺半群的冰山一角,但我无法真正地围绕这些(除了简单的monadic endomorphisms).但谷歌搜索monads monoids出现了相当多的变化.