将状态单子与余状态协函子结合

Question

如何将状态单子S ->（A，S）与余状态余单（E->A，E）组合？

我尝试了明显的组合S -> ((E->A，E)，S)和（E->S->（A，S），E），但在任一情况下，我都不知道如何为组合定义操作（return，extract等）。

- Bob

---

你的意思是这个应该同时是一个单子和余子？我觉得这有点过于乐观了，认为这是可能的... - leftaroundabout

没有特别的理由相信：(a) 单子的组合是单子，(b) 余单子的组合是余单子，或者(c) 任何类型都既是单子又是余单子（注意 Identity 是单子，这是非常极端的）。因此，期望单子和余单子的组合是单子或余单子，更不用说两者都是了，是相当冒险的。不幸的是，分配律只有在 State CoState 和 CoState State 相同时才成立，但现实情况既不是这样，也没有帮助。 - J. Abrahamson

@Bob，你可以在不同的上下文中使用它们，因为它们各自擅长什么？你的问题听起来像是“我如何编写一个功能程序，即使我不能将Bool和Int结合起来，也要同时使用它们？” - luqui

当你谈论Uustalu和Vene中单子和余单子之间的分配律时，通常并不是指一个单子及其特定对偶余单子。在这种情况下，你需要使用分配律。 - J. Abrahamson

这个可能会更易懂一些：http://blog.sigfpe.com/2008/03/transforming-comonad-with-monad.html - J. Abrahamson

Answer 1

将两个单子(O和I)结合起来可以形成一个单子，如果O或I有一个extract方法，即它们是copointed的。每个共同单子都是copointed的。如果O和I都是copointed，则有两种不同的“自然”方式可以获得单子，这两种方式可能不等价。

你有：

unit_O :: a -> O a
join_O :: O (O a) -> O a
unit_I :: a -> I a
join_I :: I (I a) -> I a

这里我添加了_O和_I作为说明。在实际的Haskell代码中，它们不会存在，因为类型检查器可以自行解决。

你的目标是展示O（I O（I a））是一个monad。让我们假设O是copointed，即存在一个函数extract_O :: O a -> a。

那么我们有：

unit :: a -> O (I a)
unit = unit_O . unit_I
join :: O (I (O (I a))) -> O (I a)

当然，实施join存在问题。我们采用以下策略：

• fmap在外部的O上执行
• 使用extract_O来去除内部的O
• 使用join_I来组合这两个I单子

这带领我们到

join = fmap_O $ join_I . fmap_I extract

为了让这个工作起来，你还需要定义。

newtype MCompose O I a = MCompose O (I a)

将相应的类型构造函数和析构函数添加到上面的定义中。

另一种选择是使用extract_I而不是extract_O。这个版本甚至更简单:

join = join_O . fmap_O extract_I

这定义了一个新的单子。我假设你可以以同样的方式定义一个新的余单子，但我没有尝试过。

- Erik Schnetter

---

具体来说，当我们将这个通用结果应用于状态单子和余状态余单子时，我们会得到什么？ - Bob

漂亮的展示！顺便问一下，在Haskell中是否存在一个copointed Functor，它不能是Comonad？ - mnish

我正在尝试证明对于一个指向对象的函子F，forall r.F(r)->r上的任何自然单子结构（在F上自然）都会导致F上的一个余单子。你认为这是正确的吗？ - mnish

Answer 2

正如其他答案所示，组合 S -> ((E->A, E), S) 和 (E->S->(A, S), E) 都同时具有Monad和Comonad实例。实际上，给出一个Monad/Comonad实例等价于在其点 ∀r.r->f(r) 或其余点 ∀r.f(r)->r 上赋予monoid结构，至少在经典的非构造意义下是这样（我不知道构造性答案）。这个事实表明，实际上一个Functor f 有很大的机会既可以是Monad又可以是Comonad，只要它的点和余点是非平凡的。

然而，真正的问题是这样构建的Monad/Comonad实例是否具有自然的计算/范畴意义。在这种情况下，我会说“不”，因为您似乎没有先验知识来了解如何以适合您的计算需求的方式组合它们。

将两个（共）单子组合的标准范畴方法是通过伴随。让我总结一下你的情况：

      Fₑ         Fₛ
      -->       -->
Hask  ⊣   Hask  ⊣ Hask
      <--       <--
      Gₑ         Gₛ

Fₜ(a) = (a,t)
Gₜ(a) = (t->a)

Fₜ ⊣ Gₜ 的证明：

Fₜ(x) -> y   ≃
(x,t) -> y   ≃
x  -> (t->y) ≃
x  -> Gₜ(y)

现在你可以看到状态单子(s->(a,s)) ≃ (s->a, s->s)就是GₛFₛ的组合，而共态余单子则是FₑGₑ。这个对偶关系说明Hask可以被看作(co)state (co)algebras模型。

现在，“对偶关系也可以组合”。例如：

FₛFₑ(x) -> y ≃
Fₑ(x)   -> Gₛ(y) ≃
x       -> GₑGₛ(y)

所以 FₛFₑ ⊣ GₑGₛ。这提供了一对单子和余单子，即

T(a) = GₑGₛFₛFₑ(a)
     = GₑGₛFₛ(a,e)
     = GₑGₛ(a,e,s)
     = Gₑ(s->(a,e,s))
     = e->s->(a,e,s)
     = ((e,s)->a, (e,s)->(e,s))

G(a) = FₛFₑGₑGₛ(a)
     = FₛFₑGₑ(s->a)
     = FₛFₑ(e->s->a)
     = Fₛ(e->s->a,e)
     = (e->s->a,e,s)
     = ((e,s)->a, (e,s))

T只是带有状态 (e,s) 的状态单子，G是带有反状态(e,s)的共状态余子，因此它们确实具有非常自然的含义。

组合伴随是一种自然、频繁出现的数学操作。例如，在拓扑空间上的层（一种允许在“类型层面”进行复杂（非自由）构造的笛卡尔闭类别）之间的一个几何态射被定义为一对伴随，仅要求其左伴随是左精确的（即保持有限极限）。如果这些层是拓扑空间上的层，则将伴随组合简单地对应于组合（唯一的）连续基变换映射（相反方向），具有非常自然的含义。

另一方面，直接组合单子/余子似乎在数学中非常少见。这是因为通常认为（余）单子是（余）代数理论的载体，而不是模型。在这种解释下，相应的伴随就是模型，而不是单子。问题在于，组合两个理论需要另一个理论，一个关于如何组合它们的理论。例如，想象一下组合两个幺半群理论。那么你可能会得到至少两个新的理论，即列表的理论或环状代数的理论，其中两种二元运算分别分配。从先验上看，它们都不比另一个更好/更自然。这就是“单子无法组合”的含义；它并不表示该组合不能成为单子，但它确实表示需要另一个关于如何组合它们的理论。

相反，组合伴随自然地产生另一个伴随，因为通过这样做，您隐含地指定了组合两个给定理论的规则。因此，通过取组合伴随的单子，您将获得还指定组合规则的理论。

- mnish