无Monad Transformer的显式Monad实例探寻

咱们先梳理下背景：Reader、Writer、State这些标准Monad都有配套的Monad Transformer，但它们的实现路子各不相同。目前根本没有通用方法能直接从一个带Monad实例的类型构造器，自动生成对应的Transformer——这就意味着，我们没法拍胸脯保证，任意按业务需求设计的Monad都能找到对应的Transformer。那现在的问题是：对于那些显式定义、完全用纯函数实现的Monad，是不是一定存在对应的Transformer实例？

相关背景参考 #

首先得明确一个关键事实：两个Monad的函子组合不一定还是Monad。比如把Monad M和N组合成M(N a)或者N(M a)，结果可能是合法Monad，也可能不是。但这类例子只能说明“没有通用的Transformer构造方法”，既没法指导我们怎么构造Transformer，也没法证明某个特定Monad到底有没有对应的Transformer。

另外还有个特殊情况：IO Monad是没有对应的Transformer的。假设存在IOT，当我们把它应用到List Monad时，lift []需要撤销IO之前执行的副作用，但IO的副作用是不可撤销的——不过IO是底层库定义的不透明“魔法”类型，并非显式的纯函数实现的类型构造器，所以不在我们这次讨论的范围内。

现有讨论与待解疑问 #

对于Haskell库中那些显式定义的纯Monad，我们总能通过调整实现找到对应的Transformer。比如曾经的ListT有设计缺陷，后来修改定义就修复了。但这是不是意味着所有纯函数实现的显式Monad都能做到？

举个具体的例子，假设我们定义这样一个类型构造器：

type Q u v a = ((u -> (a, Maybe a)) -> v) -> u -> (a, Maybe a)

我们可以为类型参数a实现合法的Monad实例，而且return和join都是纯函数。那这个Q u v是否存在对应的Monad Transformer QT u v，满足QT u v Id等价于Q u v，并且严格符合Transformer的所有定律？目前我们还不清楚怎么显式构造出QT。

要彻底解答这个问题，我们需要做到以下二者之一： #

• 提供通用构造算法：能处理任意给定的、由->、元组、Either组合而成的类型构造器（比如type F a = r -> Either (a, a) (a, a, Maybe a)）及其Monad实例实现，自动推导出对应的Transformer代码；
• 构造明确反例：找到一个显式定义的、纯函数实现的合法Monad类型构造器，并且能严格证明它不存在对应的Monad Transformer。

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