编程中幺半群/半群的示例
众所周知，幺半群在编程中非常普遍。它们如此普遍且如此有用，以至于我作为一个“爱好项目”，正在开发一个完全基于它们的属性（分布式数据聚合）的系统。为了使系统有用，我需要有用的幺半群:)
我已经知道这些：
- 数字或矩阵和
- 数字或矩阵乘积
- 具有顶部或底部元素的全序下的最小值或最大值（更一般地，在有界格子中连接或相遇，或者更一般地说，类别中的乘积或余积）
- 集并集映射
- 并集，其中使用幺半群连接冲突的值
- 有限集子集的交集（如果我们谈论半群，则只是集交集）
- 具有有界键域的映射的交集（此处相同）
- 排序序列的合并，可能在不同的幺半群/半群中加入键相等的值
- 排序列表的有界合并（与上面相同，但我们取结果的前 N 个）
- 两个幺半群或半群的笛卡尔积
- 列表连接
- 同态组合。
现在，让我们将操作的准属性定义为满足等价关系的属性。例如，如果我们认为相同长度或具有相同内容的列表在排列上是等价的，则列表串联是准交换的。
以下是一些拟幺半群、拟交换幺半群和半群：
- 任何（a+b = a 或 b，如果我们认为载体集的所有元素都是等价的）
- 任何满足谓词（a+b = a 和b 为非空且满足某个谓词 P，如果没有满足某个谓词，则为 null，如果我们认为所有满足 P 的元素都是等价的）
- 随机样本的有界混合（xs+ys = 来自 xs 和 ys 串联的大小为 N 的随机样本； ；如果我们认为任何两个与整个数据集具有相同分布的样本是等效的）
- 加权随机样本的有界混合
- 我们称之为“拓扑合并”：给定两个非循环且不矛盾的依赖关系图，一个包含所有依赖关系的图两者均指定。例如，列表“串联”可能会产生任何排列，其中每个列表的元素按顺序排列（例如，123+456=142356）。
还有哪些确实存在？
It is well-known that monoids are stunningly ubiquitous in programing. They are so ubiquitous and so useful that I, as a 'hobby project', am working on a system that is completely based on their properties (distributed data aggregation). To make the system useful I need useful monoids :)
I already know of these:
- Numeric or matrix sum
- Numeric or matrix product
- Minimum or maximum under a total order with a top or bottom element (more generally, join or meet in a bounded lattice, or even more generally, product or coproduct in a category)
- Set union
- Map union where conflicting values are joined using a monoid
- Intersection of subsets of a finite set (or just set intersection if we speak about semigroups)
- Intersection of maps with a bounded key domain (same here)
- Merge of sorted sequences, perhaps with joining key-equal values in a different monoid/semigroup
- Bounded merge of sorted lists (same as above, but we take the top N of the result)
- Cartesian product of two monoids or semigroups
- List concatenation
- Endomorphism composition.
Now, let us define a quasi-property of an operation as a property that holds up to an equivalence relation. For example, list concatenation is quasi-commutative if we consider lists of equal length or with identical contents up to permutation to be equivalent.
Here are some quasi-monoids and quasi-commutative monoids and semigroups:
- Any (a+b = a or b, if we consider all elements of the carrier set to be equivalent)
- Any satisfying predicate (a+b = the one of a and b that is non-null and satisfies some predicate P, if none does then null; if we consider all elements satisfying P equivalent)
- Bounded mixture of random samples (xs+ys = a random sample of size N from the concatenation of xs and ys; if we consider any two samples with the same distribution as the whole dataset to be equivalent)
- Bounded mixture of weighted random samples
- Let's call it "topological merge": given two acyclic and non-contradicting dependency graphs, a graph that contains all the dependencies specified in both. For example, list "concatenation" that may produce any permutation in which elements of each list follow in order (say, 123+456=142356).
Which others do exist?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
商幺半群是形成幺半群（准类群？）的另一种方式：给定幺半群 M 和等价物关系〜与乘法兼容，它给出了另一个幺半群。例如：
具有并集的有限多重集：如果 A* 是自由幺半群（具有串联的列表），~ 是“是”关系的排列，则 A*/~ 是自由交换
具有并集的有限集：如果 ~ 被修改为忽略元素的计数（因此“aa” ~ “a”），则 A*/~ 是一个自由交换幂等幺半群。
句法幺半群：任何正则语言都会产生句法幺半群，它是通过“语言不可区分性”关系获得 A* 的商。 这里是这个想法的手指树实现。例如，语言 {a3n:n natural} 将 Z3 作为句法幺半群。
商幺半群自动具有同态 M -> M/~ 是满射的。
“对偶”结构是子幺半群。它们具有同态 A -> 。 M 是单射的。
幺半群的另一种构造是张量积。
幺半群允许通过 O(log n) 平方和快速并行前缀和计算来求幂。它们也在 Writer monad 中使用。
Quotient monoid is another way to form monoids (quasimonoids?): given monoid M and an equivalence relation ~ compatible with multiplication, it gives another monoid. For example:
finite multisets with union: if A* is a free monoid (lists with concatenation), ~ is "is a permutation of" relation, then A*/~ is a free commutative monoid.
finite sets with union: If ~ is modified to disregard count of elements (so "aa" ~ "a") then A*/~ is a free commutative idempotent monoid.
syntactic monoid: Any regular language gives rise to syntactic monoid that is quotient of A* by "indistinguishability by language" relation. Here is a finger tree implementation of this idea. For example, the language {a3n:n natural} has Z3 as the syntactic monoid.
Quotient monoids automatically come with homomorphism M -> M/~ that is surjective.
A "dual" construction are submonoids. They come with homomorphism A -> M that is injective.
Yet another construction on monoids is tensor product.
Monoids allow exponentation by squaring in O(log n) and fast parallel prefix sums computation. Also they are used in Writer monad.
Haskell 标准库因其类型类使用实际数学术语而受到赞扬和攻击。 （在我看来这是一件好事，因为没有它我永远不会知道什么是幺半群！）。无论如何，您可以查看 http:// /www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Monoid.html 更多示例：
，最后一个也是如此
后者只是与单子和箭头相关的整个幺半群家族的冰山一角，但我无法真正理解这些（除了简单的单子同态）。但是在 google 上搜索
monads monoids会出现很多结果。The Haskell standard library is alternately praised and attacked for its use of the actual mathematical terms for its type classes. (In my opinion it's a good thing, since without it I'd never even know what a monoid is!). In any case, you might check out http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Monoid.html for a few more examples:
and likewise for last
The latter is just the tip of the iceberg of a whole family of monoids related to monads and arrows, but I can't really wrap my head around these (other than simply monadic endomorphisms). But a google search on
monads monoidsturns up quite a bit.交换幺半群的一个真正有用的例子是逻辑和约束语言的统一。请参阅计算机编程的概念、技术和模型的第 2.8.2.2 节 获取可能的统一算法的精确定义。
祝你的语言好运！我正在使用并行语言做类似的事情，使用幺半群来合并并行计算的子结果。
A really useful example of a commutative monoid is unification in logic and constraint languages. See section 2.8.2.2 of Concepts, Techniques and Models of Computer Programming for a precise definition of a possible unification algorithm.
Good luck with your language! I'm doing something similar with a parallel language, using monoids to merge subresults from parallel computations.
任意长度罗马数值计算。
https://gist.github.com/4542999
Arbitrary length Roman numeral value computation.
https://gist.github.com/4542999