能否结合mfix与cofix计算单子与余单子的混合不动点？

我们可以基于给定的mfix、cofix和分配律distr，构造出类型为w (w a -> m a) -> m a的函数，下面给出两种可行的实现方式：

方式一：结合mfix与分配律distr #

利用余单子的核心操作extract :: w a -> a（余单子定义必备），推导步骤如下：

1. 对于输入f :: w (w a -> m a)，先定义辅助函数loop :: w a -> m (w a)：
   • 对任意wa :: w a，fmap ($ wa) f会将f中每个w a -> m a的函数作用于wa，得到w (m a)。
   • 通过分配律distr将w (m a)转换为m (w a)，即loop wa = distr (fmap ($ wa) f)。
2. 将loop传入mfix，得到m (w a)（mfix会找到w a类型的不动点）。
3. 最后用extract提取w a中的a，通过Monad的>>=将m (w a)转换为m a。

完整实现代码：

mixfix :: (Monad m, Comonad w) => (w (m a) -> m (w a)) -> w (w a -> m a) -> m a
mixfix distr f = mfix (\wa -> distr (fmap ($ wa) f)) >>= extract

方式二：同时结合mfix与cofix #

如果需要同时用到两个不动点算子，构造逻辑如下：

1. 把输入f :: w (w a -> m a)中的每个g :: w a -> m a转换为w (m a) -> m a的函数：
   • 对任意wma :: w (m a)，定义h wma = mfix (\a -> g (fmap (const a) wma))：这里fmap (const a) wma将w (m a)映射为w a，传入g后得到a -> m a，再用mfix找到该函数的不动点。
2. 通过fmap将这个转换应用到整个w结构上，得到w (w (m a) -> m a)，正好匹配cofix的参数类型。
3. 调用cofix即可得到m a类型的结果。

实现代码：

mixfix' :: (Monad m, Comonad w) => w (w a -> m a) -> m a
mixfix' f = cofix $ fmap (\g wma -> mfix (\a -> g (fmap (const a) wma))) f

如果结合分配律distr，还可以对这个实现进行优化（比如替换fmap (const a) wma为更高效的余单子操作），但核心逻辑已同时用到mfix和cofix。

不动点语义验证 #

两种构造均符合不动点的直观性质：

• 对于mixfix，有mixfix distr f ≡ distr (fmap ($ duplicate (mixfix distr f)) f) >>= extract（利用余单子的duplicate特性）。
• 对于mixfix'，有mixfix' f ≡ (\g wma -> mfix (\a -> g (fmap (const a) wma))) (extract f) (duplicate (mixfix' f))，满足余单子不动点的定义。

内容的提问来源于stack exchange，提问作者Bob