28

众所周知，幺半群在编程中无处不在。它们无处不在，非常有用，以至于我作为一个“爱好项目”，正在开发一个完全基于它们的属性（分布式数据聚合）的系统。为了使系统有用，我需要有用的幺半群:)

我已经知道这些：

  • 数值或矩阵求和
  • 数值或矩阵乘积
  • 具有顶部或底部元素的总订单下的最小值或最大值（更一般地，在有界格中加入或相遇，或者更一般地，产品或副产品在一个类别中）
  • 设置联合
  • 使用 monoid 连接冲突值的映射联合
  • 有限集的子集的交集（或者如果我们谈论半群，则只是集的交集）
  • 地图与有界关键域的交集（此处相同）
  • 排序序列的合并，可能在不同的幺半群/半群中加入键相等的值
  • 排序列表的有界合并（同上，但我们取结果的前 N ​​个）
  • 两个幺半群或半群的笛卡尔积
  • 列表连接
  • 内同构组合。

现在，让我们将操作的准属性定义为符合等价关系的属性。例如，如果我们认为等长的列表或具有相同内容直到置换的列表是等价的，则列表连接是准交换的。

下面是一些准幺半群和准交换幺半群和半群：

  • 任意（a+b = a 或 b，如果我们认为载体集合的所有元素都是等价的）
  • 任何令人满意的谓词（a+b = a 和 b 中的一个非空且满足某个谓词 P，如果没有满足则为空；如果我们认为所有满足 P 的元素等价）
  • 随机样本的有界混合（xs+ys = xs 和 ys 串联的大小为 N 的随机样本；如果我们认为与整个数据集具有相同分布的任意两个样本是等价的）
  • 加权随机样本的有界混合
  • 让我们称之为“拓扑合并”：给定两个非循环且不矛盾的依赖关系图，一个包含两者中指定的所有依赖关系的图。例如，列表“连接”可能会产生任何排列，其中每个列表的元素按顺序排列（例如，123+456=142356）。

还有哪些其他存在？

4

4 回答 4

6

商幺半群是形成幺半群（拟似幺？）的另一种方式：给定幺半群 M 和一个等价关系 ~ 与乘法兼容，它给出另一个幺半群。例如：

  • 具有联合的有限多重集：如果 A* 是一个自由幺半群（具有串联的列表），~ 是“是”关系的“排列”，那么 A*/~ 是一个自由交换幺半群。

  • 带有 union 的有限集：如果 ~ 被修改为忽略元素的数量（所以 "aa" ~ "a"），那么 A*/~ 是一个自由交换幂等幺半群。

  • 句法幺半群：任何常规语言都会通过“语言不可区分性”关系产生与 A* 商的句法幺半群。这是这个想法的手指树实现。例如，语言 {a 3n :n natural} 有 Z 3作为句法幺半群。

商幺半群自动带有满射的同态 M -> M/~。

“对偶”结构是亚类。它们具有单射的同态 A -> M。

在幺半群上的另一种构造是张量积。

Monoids 允许通过 O(log n) 中的平方和快速并行前缀和计算来求幂。它们也用于 Writer monad。

于 2010-03-20T23:01:40.817 回答
5

Haskell 标准库因其在其类型类中使用实际数学术语而受到赞扬和攻击。（在我看来这是一件好事，因为没有它我永远都不知道幺半群是什么！）。在任何情况下，您都可以查看http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Monoid.html以获得更多示例：

  • 任何幺半群的对偶都是一个幺半群：给定 a+b，定义一个新操作 ++，其中 a++b = b+a
  • 布尔值的合取和析取
  • 在 Maybe monad （又名 Ocaml 中的“选项”）上，第一个也是最后一个。那是，
    第一个（只是一个）b = 只是一个
首先什么都没有 b = b
    最后也是

后者只是与单子和箭头相关的整个幺半群家族的冰山一角，但我无法真正理解这些（除了简单的单子自同态）。但是谷歌搜索monads monoids出现了很多。

于 2010-03-20T20:04:12.090 回答
1

可交换幺半群的一个非常有用的例子是逻辑和约束语言的统一。有关可能的统一算法的精确定义，请参见“计算机编程的概念、技术和模型”的第 2.8.2.2 节。

祝你的语言好运！我正在使用并行语言做类似的事情，使用 monoids 来合并来自并行计算的子结果。

于 2012-05-28T14:32:15.660 回答
0

任意长度罗马数值计算。 https://gist.github.com/4542999

于 2013-01-16T17:07:38.567 回答