预合成 monad 转换器
Precomposing monad transformers
假设我有两个 monad 转换器
T1 :: (* -> *) -> * -> *
T2 :: (* -> *) -> * -> *
有实例
instance MonadTrans T1
instance MonadTrans T2
还有一些
X :: (((* -> *) -> * -> *) -> ((* -> *) -> * -> *) -> * -> *)
比如
newtype X t1 t2 a b = X { x :: t1 (t2 a) b }
我想为此定义一些东西
instance (MonadTrans t1, MonadTrans t2) => MonadTrans (X t1 t2) where
lift = X . lift . lift
以便我可以使用 lift 将 m a 提升为 X T1 T2 m a?
这里的问题似乎是 lifts 作用于一些 monad Monad m => m a，我不能保证在中间步骤中产生。但这让我感到困惑。我正在提供 lift 的实现，所以我可以假设我有 Monad m => m a，所以我应用最右边的 lift 并得到 T1 m a 我一无所知，但不应该暗示 T1 m 是 Monad？如果不是，为什么我不能简单地将其添加到我的实例的约束中
instance ( MonadTrans t1
, MonadTrans t2
, Monad (t2 m) ) => MonadTrans (X t1 t2) where ...
这也不行。我有一种直觉，上面我说的是 "should there be t1, t2, m such that ..." 这太弱了，无法证明 X t1 t2 是一个转换器（适用于 any/all Monad m）。但这对我来说仍然没有多大意义，一个有效的 monad 转换器在应用于 monad 时能否产生非 monad？如果没有，我应该能够摆脱 MonadTrans (X t1 t2).
的实例
是否有我无法做到的技巧，或者是否有无法完成的原因（理论上或当前编译器支持的限制）。
这个含义是否对应于
以外的任何东西
instance (MonadTrans t, Monad m) => Monad (t m) where
return = lift . return
a >>= b = ... # no sensible generic implementation
哪个会与其他实例重叠/无法提供特定绑定？这不能通过一些间接的方式解决吗？使 returnT :: Monad m => a -> t m a 和 bindT :: Monad m => t m a -> (a -> t m b) -> t m b 成为 MonadTrans 的一部分，这样就可以写
instance MonadTrans (StateT s) where
lift = ...
returnT = ...
bindT = ...
...
instance (MonadTrans t, Monad m) => Monad (t m) where
return = returnT
a >>= b = a `bindT` b
这种实例由于重叠目前无效，但是它们是否可行，有用？
首先：你想要的是不可能的。您已经正确地识别了问题：即使 m 是一个单子，而 t — 一个转换器，也没有人保证 t m 会是一个单子。
另一方面，通常是这样。但是——至少在理论上——并非总是如此，所以，你必须以某种方式标记它出现的场合。这意味着用您必须自己定义的另一种类型 class 的实例来标记它。让我们看看它是如何工作的。
我们将从新的名称开始 class:
class MonadTrans t => MonadTransComposeable t where
现在，where 什么？我们要生成一个 Monad (t m) 实例。不幸的是，这不是我们能做的。 Class 实例虽然只是数据，但与其他所有数据不被视为同一类型的数据；我们无法创建生成它们的函数。所以，我们必须以某种方式解决这个问题。但是如果我们有这样的东西，那么 class 就很简单了
class MonadTrans t => MonadTransComposeable t where
transformedInstance :: Monad m => MonadInstance (t m)
现在让我们定义MonadInstance。我们要确保如果有 MonadInstance n，那么 n 是一个单子。 GADTs 来救援：
data MonadInstance n where MonadInstance :: Monad n => MonadInstance n
请注意 MonadInstance 构造函数有一个上下文，它保证我们不能在 n 不是 Monad 的情况下创建 MonadInstance n。
我们现在可以定义 MonadTransComposeable 的实例：
instance MonadTransComposeable (StateT s) where
transformedInstance = MonadInstance
它会起作用，因为它已经在 transformers 包中建立，只要 m 是一个单子，StateT m 也是一个单子。因此，MonadInstance构造函数是有道理的。
现在我们可以组合 MonadTrans 和 MonadTransComposeable。使用您自己的定义
newtype X t1 (t2 :: (* -> *) -> (* -> *)) m a = X { x :: t1 (t2 m) a }
我们可以定义一个实例。我们现在可以证明 t2 m 是一个单子；它不是自动的，我们必须告诉 Haskell 使用哪个 transformedInstance，但这并不难：
instance (MonadTrans t1, MonadTransComposeable t2) => MonadTrans (X t1 t2) where
lift :: forall m a. (Monad m) => m a -> X t1 t2 m a
lift ma =
case transformedInstance :: MonadInstance (t2 m) of
MonadInstance -> X (lift (lift ma))
现在，让我们做点有趣的事吧。让我们告诉 Haskell，只要 t1 和 t2 是 "good"（可组合的）monad 转换器，X t1 t2 也是。
和以前一样，很简单：
instance (MonadTransComposeable t1, MonadTransComposeable t2) => MonadTransComposeable (X t1 t2) where
transformedInstance = MonadInstance
与 StateT 相同。问题是现在 Haskell 会抱怨它不知道 X t1 t2 m 是否真的是一个 monad。这是公平的——我们没有定义一个实例。让我们这样做吧。
我们将使用 t1 (t2 m) 是 monad 的事实。所以，我们明确说明：
transformedInstance2 :: forall t1 t2 m. (MonadTransComposeable t1, MonadTransComposeable t2, Monad m) => MonadInstance (t1 (t2 m))
transformedInstance2 =
case transformedInstance :: MonadInstance (t2 m) of
MonadInstance -> transformedInstance
现在，我们将定义一个 Monad (X t1 t2 m) 实例。由于将 Monad 设为 Applicative 的子 class 的愚蠢决定，我们无法在一条语句中完成此操作，而必须通过 Functor 和 Applicative, 但并不难:
instance (MonadTransComposeable t1, MonadTransComposeable t2, Monad m) => Functor (X t1 t2 m) where
fmap h (X ttm) =
case transformedInstance2 :: MonadInstance (t1 (t2 m)) of
MonadInstance -> X (fmap h ttm)
instance (MonadTransComposeable t1, MonadTransComposeable t2, Monad m) => Applicative (X t1 t2 m) where
pure a =
case transformedInstance2 :: MonadInstance (t1 (t2 m)) of
MonadInstance -> X (pure a)
(X ttf) <*> (X tta) =
case transformedInstance2 :: MonadInstance (t1 (t2 m)) of
MonadInstance -> X (ttf <*> tta)
最后
instance (MonadTransComposeable t1, MonadTransComposeable t2, Monad m) => Monad (X t1 t2 m) where
X tta >>= f =
case transformedInstance2 :: MonadInstance (t1 (t2 m)) of
MonadInstance -> X (tta >>= \a -> case f a of X ttb -> ttb)
[C]an a valid monad transformer produce a non-monad when applied to a monad?
没有。 monad 转换器是一种类型构造函数 t :: (* -> *) -> (* -> *)，它将 monad 作为参数并生成一个新的 monad。
虽然我希望看到更明确的说明，the transformers documentation does say "A monad transformer makes a new monad out of an existing monad", and it's implied by the MonadTrans laws:
lift . return = return
lift (m >>= f) = lift m >>= (lift . f)
显然，只有当 lift m 确实是一元计算时，这些定律才有意义。正如您在评论中指出的那样，如果我们有 non-lawful 个实例需要应对，那么所有的赌注都会落空。这是 Haskell，不是 Idris，所以我们习惯于使用文档礼貌地要求满足法律，而不是使用类型强制要求它。
更多 "modern" MonadTrans 可能需要明确证明 t m 是单子，而 m 是单子。这里我用 the "entailment" operator :- from Kmett's constraints library 表示 Monad m 表示 Monad (t m):
class MonadTrans t where
transform :: Monad m :- Monad (t m)
lift :: Monad m => m a -> t m a
（这与@MigMit 在他的回答中提出的想法大致相同，但使用了 off-the-shelf 个组件。）
为什么 transformers 中的 MonadTrans 没有 transform 成员？ GHC 编写时不支持 :- 运算符（ConstraintKinds 扩展名尚未发明）。世界上有很多代码依赖于 MonadTrans 而没有 transform，所以我们不能真正返回并在没有 a really good reason 的情况下添加它，实际上 transform 方法并不能给你带来多少好处。
有一个众所周知的理论说 monad 通常是不可组合的。也就是说，给定任意两个单子 t 和 u 不能保证 t ○ u 是一个单子，其中 (t ○ u) a = t (u a)。这似乎是此预合成不可用的最终原因。
道理很简单。首先，请注意任何 monad 都可以写成 identity monad 的变换。那么，任意两个monad都可以翻译成X的形式。这对应于它们的组合，这通常是不允许的，所以我们知道 X 通常不应该被允许。
设 Id 为身份单子，
newtype Id a = Id a
并让组合由以下公式给出：
newtype t ○ u a = Comp (t (u a))
另外，对于任何单子 t，Id 的组合等于 t。
t ○ Id ~ t ~ Id ○ t
然后，我们研究X t u m a的情况，其中t u是Id的组合。类型和构造由
给出
X (t ○) (Id ○ (u ○)) (Id ○ m) a
= X ((t ○) (Id ○ (u ○ (Id ○ m)) a)
而 RHS 构造函数等同于
~ X ((t ○) (u ○ m) a)
具有类型
X (t ○) (u ○) m a
所以部分应用X (t ○) (u ○)对应于任意两个单子的组合，这是不允许的。
这并不是说我们不能组合 monad，而是解释了为什么我们需要分别来自 Benjamin Hodgson 和 MigMit 的 transform 或 MonadTransComposable 等方法。
我已将其设为社区 Wiki，如我所料，fast-and-loose 真正知道自己在做什么的人可以大大改进证明。
假设我有两个 monad 转换器
T1 :: (* -> *) -> * -> *
T2 :: (* -> *) -> * -> *
有实例
instance MonadTrans T1
instance MonadTrans T2
还有一些
X :: (((* -> *) -> * -> *) -> ((* -> *) -> * -> *) -> * -> *)
比如
newtype X t1 t2 a b = X { x :: t1 (t2 a) b }
我想为此定义一些东西
instance (MonadTrans t1, MonadTrans t2) => MonadTrans (X t1 t2) where
lift = X . lift . lift
以便我可以使用 lift 将 m a 提升为 X T1 T2 m a?
这里的问题似乎是 lifts 作用于一些 monad Monad m => m a，我不能保证在中间步骤中产生。但这让我感到困惑。我正在提供 lift 的实现，所以我可以假设我有 Monad m => m a，所以我应用最右边的 lift 并得到 T1 m a 我一无所知，但不应该暗示 T1 m 是 Monad？如果不是，为什么我不能简单地将其添加到我的实例的约束中
instance ( MonadTrans t1
, MonadTrans t2
, Monad (t2 m) ) => MonadTrans (X t1 t2) where ...
这也不行。我有一种直觉，上面我说的是 "should there be t1, t2, m such that ..." 这太弱了，无法证明 X t1 t2 是一个转换器（适用于 any/all Monad m）。但这对我来说仍然没有多大意义，一个有效的 monad 转换器在应用于 monad 时能否产生非 monad？如果没有，我应该能够摆脱 MonadTrans (X t1 t2).
是否有我无法做到的技巧，或者是否有无法完成的原因（理论上或当前编译器支持的限制）。
这个含义是否对应于
以外的任何东西instance (MonadTrans t, Monad m) => Monad (t m) where
return = lift . return
a >>= b = ... # no sensible generic implementation
哪个会与其他实例重叠/无法提供特定绑定？这不能通过一些间接的方式解决吗？使 returnT :: Monad m => a -> t m a 和 bindT :: Monad m => t m a -> (a -> t m b) -> t m b 成为 MonadTrans 的一部分，这样就可以写
instance MonadTrans (StateT s) where
lift = ...
returnT = ...
bindT = ...
...
instance (MonadTrans t, Monad m) => Monad (t m) where
return = returnT
a >>= b = a `bindT` b
这种实例由于重叠目前无效，但是它们是否可行，有用？
首先：你想要的是不可能的。您已经正确地识别了问题：即使 m 是一个单子，而 t — 一个转换器，也没有人保证 t m 会是一个单子。
另一方面，通常是这样。但是——至少在理论上——并非总是如此，所以，你必须以某种方式标记它出现的场合。这意味着用您必须自己定义的另一种类型 class 的实例来标记它。让我们看看它是如何工作的。
我们将从新的名称开始 class:
class MonadTrans t => MonadTransComposeable t where
现在，where 什么？我们要生成一个 Monad (t m) 实例。不幸的是，这不是我们能做的。 Class 实例虽然只是数据，但与其他所有数据不被视为同一类型的数据；我们无法创建生成它们的函数。所以，我们必须以某种方式解决这个问题。但是如果我们有这样的东西，那么 class 就很简单了
class MonadTrans t => MonadTransComposeable t where
transformedInstance :: Monad m => MonadInstance (t m)
现在让我们定义MonadInstance。我们要确保如果有 MonadInstance n，那么 n 是一个单子。 GADTs 来救援：
data MonadInstance n where MonadInstance :: Monad n => MonadInstance n
请注意 MonadInstance 构造函数有一个上下文，它保证我们不能在 n 不是 Monad 的情况下创建 MonadInstance n。
我们现在可以定义 MonadTransComposeable 的实例：
instance MonadTransComposeable (StateT s) where
transformedInstance = MonadInstance
它会起作用，因为它已经在 transformers 包中建立，只要 m 是一个单子，StateT m 也是一个单子。因此，MonadInstance构造函数是有道理的。
现在我们可以组合 MonadTrans 和 MonadTransComposeable。使用您自己的定义
newtype X t1 (t2 :: (* -> *) -> (* -> *)) m a = X { x :: t1 (t2 m) a }
我们可以定义一个实例。我们现在可以证明 t2 m 是一个单子；它不是自动的，我们必须告诉 Haskell 使用哪个 transformedInstance，但这并不难：
instance (MonadTrans t1, MonadTransComposeable t2) => MonadTrans (X t1 t2) where
lift :: forall m a. (Monad m) => m a -> X t1 t2 m a
lift ma =
case transformedInstance :: MonadInstance (t2 m) of
MonadInstance -> X (lift (lift ma))
现在，让我们做点有趣的事吧。让我们告诉 Haskell，只要 t1 和 t2 是 "good"（可组合的）monad 转换器，X t1 t2 也是。
和以前一样，很简单：
instance (MonadTransComposeable t1, MonadTransComposeable t2) => MonadTransComposeable (X t1 t2) where
transformedInstance = MonadInstance
与 StateT 相同。问题是现在 Haskell 会抱怨它不知道 X t1 t2 m 是否真的是一个 monad。这是公平的——我们没有定义一个实例。让我们这样做吧。
我们将使用 t1 (t2 m) 是 monad 的事实。所以，我们明确说明：
transformedInstance2 :: forall t1 t2 m. (MonadTransComposeable t1, MonadTransComposeable t2, Monad m) => MonadInstance (t1 (t2 m))
transformedInstance2 =
case transformedInstance :: MonadInstance (t2 m) of
MonadInstance -> transformedInstance
现在，我们将定义一个 Monad (X t1 t2 m) 实例。由于将 Monad 设为 Applicative 的子 class 的愚蠢决定，我们无法在一条语句中完成此操作，而必须通过 Functor 和 Applicative, 但并不难:
instance (MonadTransComposeable t1, MonadTransComposeable t2, Monad m) => Functor (X t1 t2 m) where
fmap h (X ttm) =
case transformedInstance2 :: MonadInstance (t1 (t2 m)) of
MonadInstance -> X (fmap h ttm)
instance (MonadTransComposeable t1, MonadTransComposeable t2, Monad m) => Applicative (X t1 t2 m) where
pure a =
case transformedInstance2 :: MonadInstance (t1 (t2 m)) of
MonadInstance -> X (pure a)
(X ttf) <*> (X tta) =
case transformedInstance2 :: MonadInstance (t1 (t2 m)) of
MonadInstance -> X (ttf <*> tta)
最后
instance (MonadTransComposeable t1, MonadTransComposeable t2, Monad m) => Monad (X t1 t2 m) where
X tta >>= f =
case transformedInstance2 :: MonadInstance (t1 (t2 m)) of
MonadInstance -> X (tta >>= \a -> case f a of X ttb -> ttb)
[C]an a valid monad transformer produce a non-monad when applied to a monad?
没有。 monad 转换器是一种类型构造函数 t :: (* -> *) -> (* -> *)，它将 monad 作为参数并生成一个新的 monad。
虽然我希望看到更明确的说明，the transformers documentation does say "A monad transformer makes a new monad out of an existing monad", and it's implied by the MonadTrans laws:
lift . return = return
lift (m >>= f) = lift m >>= (lift . f)
显然，只有当 lift m 确实是一元计算时，这些定律才有意义。正如您在评论中指出的那样，如果我们有 non-lawful 个实例需要应对，那么所有的赌注都会落空。这是 Haskell，不是 Idris，所以我们习惯于使用文档礼貌地要求满足法律，而不是使用类型强制要求它。
更多 "modern" MonadTrans 可能需要明确证明 t m 是单子，而 m 是单子。这里我用 the "entailment" operator :- from Kmett's constraints library 表示 Monad m 表示 Monad (t m):
class MonadTrans t where
transform :: Monad m :- Monad (t m)
lift :: Monad m => m a -> t m a
（这与@MigMit 在他的回答中提出的想法大致相同，但使用了 off-the-shelf 个组件。）
为什么 transformers 中的 MonadTrans 没有 transform 成员？ GHC 编写时不支持 :- 运算符（ConstraintKinds 扩展名尚未发明）。世界上有很多代码依赖于 MonadTrans 而没有 transform，所以我们不能真正返回并在没有 a really good reason 的情况下添加它，实际上 transform 方法并不能给你带来多少好处。
有一个众所周知的理论说 monad 通常是不可组合的。也就是说，给定任意两个单子 t 和 u 不能保证 t ○ u 是一个单子，其中 (t ○ u) a = t (u a)。这似乎是此预合成不可用的最终原因。
道理很简单。首先，请注意任何 monad 都可以写成 identity monad 的变换。那么，任意两个monad都可以翻译成X的形式。这对应于它们的组合，这通常是不允许的，所以我们知道 X 通常不应该被允许。
设 Id 为身份单子，
newtype Id a = Id a
并让组合由以下公式给出：
newtype t ○ u a = Comp (t (u a))
另外，对于任何单子 t，Id 的组合等于 t。
t ○ Id ~ t ~ Id ○ t
然后，我们研究X t u m a的情况，其中t u是Id的组合。类型和构造由
X (t ○) (Id ○ (u ○)) (Id ○ m) a
= X ((t ○) (Id ○ (u ○ (Id ○ m)) a)
而 RHS 构造函数等同于
~ X ((t ○) (u ○ m) a)
具有类型
X (t ○) (u ○) m a
所以部分应用X (t ○) (u ○)对应于任意两个单子的组合，这是不允许的。
这并不是说我们不能组合 monad，而是解释了为什么我们需要分别来自 Benjamin Hodgson 和 MigMit 的 transform 或 MonadTransComposable 等方法。
我已将其设为社区 Wiki，如我所料，fast-and-loose 真正知道自己在做什么的人可以大大改进证明。