list monad不是免费的单曲，而是…。

Question

在一个Monad来证明他们的第12页，它写道：“容器的一个突出的例子是列表数据类型。列表可以用列表的长度和列表中的函数映射位置来表示”。

起初，我认为这个容器上的自由单子是同构的列表单。

但是在第12页上，它写到，“列表单an不是自由单an，因为列表单an不是与自由单an的一个实例同构的”。

那么，上述容器上的免费单片是什么？同构的是什么？为什么它不是同构的列表单？它能用商来表示同构吗？

Answer 1

我觉得应该小心一点。

我不认为如果M是一个自由的monad，那么应用免费的monad构造可以使您返回与M同构的东西。所以你关于“X上的自由单体是什么”的问题实际上与“什么函子是X的自由单子”无关。为了证明monad M不是一个免费的monad，我们唯一需要做的就是展示一些对M来说是正确的，但不被monad定律所暗示的平等--因为自由monad结构的含义是它保证了单一法则，而没有其他任何东西。

对于列表，有一种方法可以做到：

f False = ""
f True = "x"

g False = "x"
g True = ""

is = [False, True]

现在is >>= f = is >>= g (= "x")，尽管f != g。

另一个问题是，通过将免费构造应用到列表中，您得到了什么？作为一种直觉，考虑自由单体结构的一种方法是，它是它所转换的事物的任意(且异质的)深嵌套版本。对于列表，这意味着类似于

[[[0], [1, [2, 3], 4]], [5,6,7]]

将成为免费建筑的成员。如果你稍微考虑一下这一点，你会发现另一种想法是把它看作是一棵树，它的叶子上有数据(只有)，每个内部节点都允许有任意数量的子节点。

只是为了好玩，我们可以再次检查，我们没有验证之前的等式。这一次我们

is >>= f = ["", "x"]
is >>= g = ["x", ""]

所以我们可以走了。