问题标签 [abstract-algebra]

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

我已经知道这些：

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

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

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

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

还有哪些其他存在？

我最近开始了解函数式编程（在 Haskell 和 Scala 中）。它的功能和优雅非常迷人。

但是当我遇到使用名为 Monoid 的代数结构的 Monads 时，我很惊讶也很高兴看到我从数学中学到的理论知识被用于编程。

这个观察让我想到了一个问题：群、域或环（其他请参见代数结构）可以在编程中用于更多抽象和代码重用目的并实现类似数学的编程吗？

据我所知，名为Fortress的语言（一旦编译器完成，我肯定会更喜欢任何语言）在其库代码中定义了这些结构。但到目前为止我看到的唯一用途是我们已经熟悉的数字类型。它们还有其他用途吗？

最好的问候， ciun

给定一个整数列表，比如{2,1,1,0}我想列出该列表中在给定组下不等价的所有排列。例如，使用正方形的对称性，结果将是{{2, 1, 1, 0}, {2, 1, 0, 1}}。

下面的方法（Mathematica 8）生成所有排列，然后剔除等效的排列。我不能使用它，因为我负担不起生成所有排列，有没有更有效的方法？

更新：实际上，瓶颈在DeleteCases. 以下列表{2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0}有大约一百万个排列，计算时间为 0.1 秒。显然，消除对称性后应该有 1292 个订单，但我的方法并没有在 10 分钟内完成

在hammar 的帮助下，我制作了一个模板 Haskell 位，它可以编译

到

我现在面临一个我认为我无法通过这种方式解决的问题。

关于多项式的一个显着事实是，如果它们在模某个素数上不可约，则它们在有理数中是不可约的p。我已经有一种方法可以蛮力尝试在给定（有限）字段上分解多项式。

我想尝试为多个字段运行此功能。这是我想要的：

基本上我想尝试为大量的“除法”定义运行我的分解算法。

我认为这可能与 TH 有关，但似乎需要永远。我想知道将我的算术运算作为参数传递给它是否更容易isIrreducible？

或者，这似乎是 Newtype 模块可以提供帮助的东西，但我想不出如果不以同样困难的方式使用 TH 它将如何工作......

有人对如何最好地实现这一点有任何想法吗？

在抽象代数中，群的概念是相当基础的。要获得一个组，我们需要一组对象和一个具有3 个属性的二元运算（如果算上闭包，则为 4 个）。如果我们想在给定有限集合的情况下随机生成一个组（即随机生成一个表格，给出集合中每个可能的元素组合的结果），那么很容易破解一个单位元素，并破解逆，但似乎很难随机生成一个关联的操作。

我的问题是是否有一些（有效的）方法可以随机生成关联操作。我尝试随机生成一个操作，然后扰乱非关联关系，以便它们一次关联一个，但这似乎并没有真正收敛。有任何想法吗？

您如何使用 GAP 从乘法表中识别组的名称？我知道您可以从一组生成器中定义一个组，然后在一组内部表中查找该组：

但是如何找出组的名称[120, 34]？

范畴论和抽象代数处理函数与其他函数结合的方式。复杂性理论处理一个函数的计算难度。对我来说很奇怪，我还没有看到有人将这些研究领域结合起来，因为它们看起来很自然。有没有人这样做过？

作为一个激励性的例子，让我们看一下幺半群。众所周知，如果一个运算是一个幺半群，那么我们可以并行化这个运算。

例如在 Haskell 中，我们可以简单地定义加法是整数上的幺半群，如下所示：

现在，如果我们想计算 0 到 999 的总和，我们可以按顺序执行，如下所示：

或者我们可以并行进行

但是并行化这个幺半群才有意义，因为 mappend 在恒定时间内运行。如果不是这样呢？例如，列表是一个幺半群，其中 mappend 不会运行不固定的时间（或空间！）。我猜这就是为什么 Haskell 中没有默认的并行 mconcat 函数的原因。最好的实现取决于幺半群的复杂性。

似乎应该有一种方便的方式来描述这两个幺半群之间的差异。然后，我们应该能够用这些差异注释我们的代码，并让程序根据幺半群的复杂性自动选择要使用的最佳算法。

algebra/2.1.1.2/doc/html的文档显示了大量的类型类。

我如何声明一个有问题的结构必须配备一个交换关联运算和一个单位/恒等元素，但没有其他任何东西（逆、分布等）？

我在想

但是 Data.Monoid 的实例不应该是可交换的，我希望我的函数的用户通过查看类型来看到他们需要可交换性才能使函数工作。

一个群扩展了幺半群的想法以允许逆。这允许：

但是像自然数这样没有逆的结构呢？我在想：

与法律：

另外：

所以，我的问题是：什么是MRemove？