haskell - 如何使用自由单子(monad)来表达延续单子(monad)？

Question

假设所有的 monad 都可以用 Free 来表示。 (如果这不是真的，什么是反例，为什么)？怎么可能the continuation monad或其对应的变压器用 Free 表示或 FreeT - 对应的仿函数是什么？或者如果他们不能，原因是什么？

更新:通过表达我的意思是基本上同构到 Free F在哪里 F是我们正在寻找的仿函数，例如 Writer w与 Free ((,) w) 同构.

Answer 1

延续单子(monad)是您正在寻找的反例。我没有足够的知识来提供完整的证明，但我会给你一些引用资料以供查找。

这个想法是单子(monad)有一个与之相关的“等级”概念。 “排名”大致意思是
提供 monad 的全部功能所需的操作数。

我怀疑，除了延续派生的单子(monad)外，我们在 Haskell 中处理的所有单子(monad)都有等级，例如Identity , Maybe , State s , Either e , ..., 以及它们通过变压器的组合。例如，Identity由无操作生成，Maybe由 Nothing 生成, State s通过 get和 put s和 Either e通过 Left e . (也许这表明它们实际上都有有限的等级，或者 put s 对每个 s 都算作不同的操作，所以 State s 的等级大小为 s ，我不确定。)

自由单子(monad)当然有排名，因为 Free f由 f 编码的操作显式生成.

以下是排名的技术定义，但不是很有启发性:http://journals.cambridge.org/action/displayAbstract?aid=4759448

在这里你可以看到延续单子(monad)没有等级的说法:http://www.cs.bham.ac.uk/~hxt/cw04/hyland.pdf .我不确定他们是如何证明这一点的，但这意味着延续单子(monad)不是由任何操作集合生成的，因此不能表示为自由单子(monad)的(商)。

希望有人能来整理我的技术细节，但这是你想要的证明的结构。