如果“List”是一个幺半群，它的“set”是什么？

Question

我正在阅读类别论书籍，并决定将其应用到Haskell中。

作者将Monoid定义为:

Monoid是一个集合L，配备了一个二元操作*：LxL->L和一个在L中的特殊单元素u，使得等等......

将“List”结构作为一个Monoid，很明显二元操作是concat，单元是[]。

但是这里的M集合是什么呢？ 我尝试过L = {所有列表的集合}，但我认为这会导致“L是否在L中？”问题，这似乎与集合的问题相同。

或者我想错了吗？

编辑：正如@applicative指出的那样，Haskell的列表是称为自由幺半群的幺半群！

- Andriy Drozdyuk

---

在数学中，避免“L in L”问题的技巧是从普通集合论（泽尔默洛-弗雷因克尔）转向将集合和类别区分开来，然后您可以谈论所有集合的类别或所有列表的类别。此外，我认为您指的是罗素悖论，它涉及到“{不包含自身的所有集合的集合}”。 - epsilonhalbe

请注意，“所有列表的集合”本身并不是一个列表，因此它不会立即遇到类似于朴素集合论中发现的矛盾。 - Ben

你是指你的二元操作要用 concat :: [[a]] -> [a]，还是 (++) :: [a] -> [a] -> [a]？实际上前者是一种单子操作，但这是相当晦涩的... - Ben Millwood

@BenMillwood，您能否解释一下concat :: [[a]] -> [a]如何成为一个幺半群操作？ - baxbaxwalanuksiwe

考虑到我五年前发表了那个评论，我只能给你提供猜测 :) 我最好的猜测是，我当时指的是 concat 是列表单子的 join 操作的想法，这在某种意义上是一种单调操作，将函子 List . List 转换为函子 List。 - Ben Millwood

Answer 1

不应该说“列表是一个Monoid”，更准确的说法是“对于所有类型a，类型[a]是一个Monoid”。因此，任何特定类型a，你的L将是L = {所有as列表的集合}。根据这个定义，显然L不能包含自己。

- sepp2k

---

那么...这个集合总是只包含一个元素吗？如果我们连接两个列表，那么这个幺半群会是什么样子呢？例如 [a] 连接 [a]... - Andriy Drozdyuk

@drozzy 我说的是类型 [a]（例如“一个由 a 组成的列表”），而不是值 [a]（例如“包含一个名为 a 的单个元素的列表”）。 - sepp2k

哦，明白了！那不就相当于一个普通的数学集合，带有并集操作和空集吗？ - Andriy Drozdyuk

@drozzy：如果这有帮助的话，它相当于在自动机课程中看到的字符串。通常写成 〈abc〉。 - Tikhon Jelvis

我喜欢这个答案，因为它是从 Haskell 直接翻译而来的。instance Monoid [a] 使用了一个普适量词 a，所以它实际上是 forall a. instance Monoid [a]。稍加调整后，这就非常接近于“对于所有类型 a，类型 [a] 是一个 Monoid”。 - John L

Answer 2

对于任何类型t，您都可以具有以下内容

L = all elements of the type [t]

使用++，L以平凡的方式成为一个单子。实际上，我们在Haskell中正式化了这一点。

class Monoid m where
   mempty  :: m
   mappend :: m -> m -> m

这是一种“类”，具有必要的操作来形成一个幺半群，因此

instance Monoid [a] where
   mempty = []
   mappend a b = a ++ b

实际上，这被称为“a的自由幺半群”。

- Philip JF

---

当你说“[t]的所有元素”时，你是指L={t1, t2, ...}还是L={{t1}, {t1, t2},...}？（其中t1，t2..的类型为t） - Andriy Drozdyuk

@drozzy：假设t = Bool，那么L = { [], [False], [True], [False, False], [False, True], [True, False], [True, True], ... }。（严格来说，您可能还想包括底部）。 - hammar

@drozzy - 它甚至不需要是有限的。例如 mappend (repeat True) (repeat False) 是完全合法的。 - John L

@JohnL 我猜我是按照自由幺半群的定义来理解的：“在集合A上的自由幺半群是其元素为所有有限序列的幺半群”，我理解这就是Haskell列表的定义。那么，Haskell列表不仅仅是自由幺半群吗？ - Andriy Drozdyuk

@drozzy：关于这个问题可以说很多，可以看看HaskellWiki和这个SO的问题。 "Total" 简单地意味着“没有底部”。祝你好运！ - danr