C++中是否有用于半环或幺半群的标准抽象？

Question

boost或其他常见的C++库是否提供类似于半环或幺半等抽象结构（例如模板类）？

我有一些算法，希望用这些抽象结构的术语来表达，但目前还没有找到任何可以使用的库。我可以自己编写，但最好能够在已经使用的库中使用，比如boost。

谢谢！

- Jason Dagit

---

哇，我以为这些词只用于折磨大学生，没想到在现实生活中也会遇到。为此点赞 :) - Sergey Kalinichenko

@dasblinkenlight 我想要实现的算法之一是在Cormen等人的《算法导论》一书中用半环和幺半群的术语写成的 :) - Jason Dagit

啊，这些家伙……他们的轻描淡写在书名上就能看出来，“算法导论”而不是“关于算法你们大部分需要知道的一切”：）：）：） - Sergey Kalinichenko

@dasblinkenlight，单子概念也出现在std::accumulate的并行版本中，例如Cilk reducer超对象（由Leiserson等人之一） - TemplateRex

Answer 1

SGI STL拥有Monoid Operation概念。例如Monoid Operation已经实现了power函数。

Boost.Graph库也定义了Monoid概念。

除了已经建议的 Programming Elements，你还可以查看由Alexander Stepanov（EoP的作者之一）编写的Notes on Programming。 笔记是免费提供的，与EoP书籍有一些重叠。

EoP和Notes之间存在样式差异-EoP非常简洁，就像数学教科书一样，但是Notes则更加“非正式”-有一些小故事等。

顺便说一句，两本书都对上面提到的power函数实现进行了讨论。

P.S. Alexander Stepanov有一些很棒的演讲：

• 编程元素
• STL及其设计原则
• A9讲座
• 最大公因数

P.P.S. Alexander A. Stepanov的论文集

- Evgeny Panasyuk

Answer 2

据我所知，C++标准库没有关于这些结构的抽象。然而，STL的发明者Alex Stepanov写了一本名为编程元素的书，其中写了许多有用的函数，可以操作单子、群、二进制运算符、一元函数等等。虽然不一定是标准，但可能是进一步探索的好起点。

希望这能帮到你！

- templatetypedef

Answer 3

Boost.Operators 提供了一种方便的方式来为类定义一组算术运算符。

预定义的概念（仅语法鸭子类型）包括环、有序环、欧几里得环、有序欧几里得环、域和有序域。您应该能够通过从适当的运算符类组派生来为半环或幺半群定义自己的类。

- TemplateRex

---

这些不是概念，而是你所说的“算术运算符组”的辅助工具。概念包括加法恒等元、乘法恒等元、加法逆元、乘法逆元等。 - Evgeny Panasyuk

@EvgenyPanasyuk 谢谢，看起来boost.operators确实没有提供身份元素。据我所知，可以使用相同的“friend”注入技巧来解决这个问题。例如，让template<class T>class MultId: field<T> {};并定义混合的operator*版本以反映交换律。 - TemplateRex

概念集中在接口上，即哪些语法是合法的，以及它具有哪些语义。这允许从具体模型抽象出算法（和其他内容）的实现。但 Boost.Operators 只是帮助实现具体模型的辅助工具。 - Evgeny Panasyuk

@EvgenyPanasyuk 谢谢，已更新答案并澄清了鸭子类型的概念。 - TemplateRex