单子和余单子计算的定点

Question

在Haskell中，给定一个单子monad m，有一个函数mfix :: (a -> m a) -> m a，可以计算单子计算的不动点。

类似地，给定一个余子comonad w，有一个函数cofix :: w (w a -> a) -> a，可以计算余子计算的不动点。

现在假设我有一个程序，它使用了既有单子m，又有余子w，它们之间有一个余单分配律distr :: w (m a) -> m (w a)。那么是否可能将mfix和cofix组合成一个类型为w (w a -> m a) -> m a的函数，以计算单子和余子计算的fixpoint？

- Bob

---

你有一个例子 w (w a -> m a) 的参数来测试我们的答案吗？另外，你考虑过使用 a = m b 特化 cofix 吗？它的类型与你要求的略有不同，但仍然非常有用。 - Li-yao Xia

@Li-yaoXia，您可以考虑使用非空列表协函w和Maybe单子m，如此一来，就能够得到本文第六节所介绍的方法。 - Bob

Answer 1

是的，实际上我们可以通过两种不同的方式定义一个合理的 wmfix :: w (w a -> m a) -> m a；一种是从 cofix 开始，另一种是从 mfix 开始。

如果我们对这两种方法进行归一化，它们基本上是相同的思路：将一些 f : w (w a -> m a) 转换成适当的 b -> b，取固定点，然后从 b 中提取出 m a。对于类似于 cofix 的方法，我们可以采用以下方式：

wmfix1 f = cofix (fmap ((. distr) . (=<<)) f)

或者直接

wmfix1 f = extract (fix g) where
    g :: w (m a) -> w (m a)
    g = extend (\x -> distr x >>= extract f)

如果我们从mfix开始，我们会得到

wmfix2 f = fmap extract (extract (fmap (mfix . (distr .)  . extend) f))

或者

wmfix2 f = fmap extract (fix h) where
    h :: m (w a) -> m (w a)
    h = (distr . extend (extract f) =<<)

很遗憾，一般情况下它们看起来并不相同，这需要一个条件，比如

fmap extract (distr (extend f x)) = f x

这个条件似乎对你提到的w = NonEmpty, m = Maybe情况成立。

- S.Klumpers

---

是的，我省略了它们，因为我觉得它们看起来不太好（而且mfix/cofix本质上是伪装的fix），但为了完整起见，我会添加它们。 - S.Klumpers

请允许我再向您提出一点挑战。是否有一种使用mfix和cofix的答案呢？ - Bob

其实你倒是可以这么做，但并不需要；如果fix是一个裸的不动点，那么mfix和cofix是某些结构下的不动点，因此wmfix在两个结构中都是“仅仅”一个不动点，而不是一个不动点的不动点。我们还期望，如果m或者w是Identity，那么wmfix应该缩减到cofix或者mfix，目前它也实现了这个条件，但是如果你同时使用它们，你会得到两个fixes。 - S.Klumpers

你的定义都有正确的类型。现在还需要看看它们是否具有正确的语义（绿灯是它们能够使用 Identity 余单子/单子来简化成 cofix/mfix）。对于 fix，你可以使用 fix f = f (fix f)。对于你的 wmfix1 和 wmfix2 是否有类似的东西呢？ - Bob

如果你问我，fix f = f (fix f) 本质上是从定义中推导出语义的。同样地，尽管 hackage 列出了 MonadFix 的法则，但当 mfix f = fix (>>= f) 时，这些法则看起来是微不足道的。那么，如果不是 wmfix f =“将f应用于wmfix f”，你会如何理解 wmfix 的语义呢？（在我的答案中，我给出了“应用f”的两种解释（g和h）。） - S.Klumpers