haskell - list monad 不是一个免费的 monad，但是……

Question

在 One Monad to Prove Them All 的第 12 页上，它写道“[容器]的一个突出示例是列表数据类型。列表可以由列表的长度和列表内的函数映射位置表示”。
起初我认为这个容器上的自由 monad 将与 list monad 同构。
但是在第 12 页上，写到“列表 monad 不是自由 monad，因为列表 monad 与自由 monad 的实例不同构”。
那么上面容器上的 free monad 是什么？它与什么同构？为什么它不与列表单子(monad)同构？它可以通过商同构吗？

Answer 1

我认为应该小心一点。
我不认为如果 M是一个自由单子(monad)，然后应用自由单子(monad)结构让你回到与M同构的东西。 .因此，您的“X 上的免费单子(monad)是什么”的问题实际上与“X 的免费单子(monad)是什么仿函数？”无关。显示 monad M不是一个自由的单子(monad)，我们唯一需要做的就是展示一些对 M 正确的相等性。但不是由单子(monad)定律暗示——因为自由单子(monad)结构的含义是它保证单子(monad)定律而不是其他任何东西。
这是对列表执行此操作的一种方法:

f False = ""
f True = "x"

g False = "x"
g True = ""

is = [False, True]

现在 is >>= f = is >>= g (= "x" ) 即使 f != g .
一个单独的问题是通过将自由构造应用于列表得到什么 monad。作为一种直觉，考虑自由 monad 构造的一种方式是，它是它所转换的事物的任意(和异构)深度嵌套版本。对于列表，这意味着像

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

将是自由 build 的成员。如果您稍微考虑一下，您会发现另一种思考方式是将其视为一棵树，其叶子(仅)具有数据，并且每个内部节点都允许有任意数量的子节点。
只是为了好玩，我们可以仔细检查一下我们没有验证之前的相等性。这次我们得到

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

所以我们可以走了。