如何使用可扩展效果获得“monad 转换器的不灵活语义”？

Question

考虑以下示例。

newtype TooBig = TooBig Int deriving Show

choose :: MonadPlus m => [a] -> m a
choose = msum . map return

ex1 :: (MonadPlus m, MonadError TooBig m) => m Int
ex1 = do
    x <- choose [5,7,1]
    if x > 5
        then throwError (TooBig x)
        else return x

ex2 :: (MonadPlus m, MonadError TooBig m) => m Int
ex2 = ex1 `catchError` handler
  where
    handler (TooBig x) = if x > 7
        then throwError (TooBig x)
        else return x

ex3 :: Either TooBig [Int]
ex3 = runIdentity . runExceptT . runListT $ ex2

ex3 的值应该是多少？如果我们使用 MTL 那么答案是 Right [7] 这是有道理的，因为 ex1 因为它抛出错误而被终止，而 handler 只是 returns 纯值 return 7 即 Right [7].

然而，在论文 “Extensible Effects: An Alternative to Monad Transformers” by Oleg Kiselyov, et al. 中，作者说这是“一个令人惊讶且不受欢迎的结果”。他们期望结果是 Right [5,7,1] 因为 handler 通过不重新抛出它从异常中恢复。本质上，他们希望 catchError 如下移动到 ex1。

newtype TooBig = TooBig Int deriving Show

choose :: MonadPlus m => [a] -> m a
choose = msum . map return

ex1 :: (MonadPlus m, MonadError TooBig m) => m Int
ex1 = do
    x <- choose [5,7,1]
    if x > 5
        then throwError (TooBig x) `catchError` handler
        else return x
  where
    handler (TooBig x) = if x > 7
        then throwError (TooBig x)
        else return x

ex3 :: Either TooBig [Int]
ex3 = runIdentity . runExceptT . runListT $ ex1

确实，这就是可扩展效果的作用。它们通过将效果处理程序移近效果源来改变程序的语义。例如，local 靠近 ask，catchError 靠近 throwError。该论文的作者将此吹捧为可扩展效果优于 monad 转换器的优势之一，声称 monad 转换器具有“不灵活的语义”。

但是，如果出于某种原因我希望结果是 Right [7] 而不是 Right [5,7,1] 怎么办？如上面的示例所示，可以使用 monad 转换器来获得这两种结果。但是，由于可扩展效果似乎总是将效果处理程序移近效果源，因此似乎无法获得结果 Right [7].

所以，问题是如何使用可扩展的效果来获得“monad 转换器的不灵活语义”？在使用可扩展效果时，是否可以防止个别效果处理程序靠近效果源？如果不是，那么这是需要解决的可扩展效果的限制吗？

Answer 1

我也对那篇论文的摘录中的细微差别感到困惑。我认为退后几步并解释该论文所属的代数效应企业背后的动机更有用。

MTL 方法在某种意义上是最明显和最通用的方法：您有一个接口（或“效果”），将其放入类型 class 中，然后收工。这种通用性的代价是它是无原则的：您不知道将接口组合在一起时会发生什么。当您实现一个接口时，这个问题最具体地出现：您必须同时实现所有接口。我们喜欢认为每个接口都可以在专用转换器中隔离实现，但是如果您有两个接口，比如 MonadPlus 和 MonadError，则由转换器 ListT 和 [=15= 实现]，为了组合它们，您还必须为 ListT 实现 MonadError 或为 ExceptT 实现 MonadPlus。这个 O(n^2) 实例问题通常被理解为“只是样板文件”，但更深层次的问题是，如果我们允许接口具有任何形状，那么就不知道该“样板文件”中可能隐藏什么危险，如果它甚至完全可以实现。

我们必须在这些接口上放置更多结构。对于“提升”的某些定义（lift from MonadTrans），我们可以通过变换器统一提升的效果正是代数效应。（另请参阅 Monad Transformers and Modular Algebraic Effects, What Binds Them Together。）

这并不是真正的限制。虽然有些接口在技术意义上不是代数的，例如 MonadError（因为 catch），但它们通常仍然可以在代数效应的框架内表示，只是字面意思更少。在限制“接口”定义的同时，我们也获得了更丰富的使用方式。

所以我认为代数效应是一种不同的、更精确的界面思考方式。作为一种思维方式，因此可以在不更改代码任何内容的情况下采用它，这就是为什么比较往往会两次查看相同的代码，并且如果不了解周围的上下文和动机就很难看出重点。如果您认为 O(n^2) 实例问题是一个微不足道的“样板”问题，那么您已经相信接口应该是可组合的原则；代数效应是围绕该原则明确设计库和语言的一种方式。

“代数效应”是一个没有固定定义的模糊概念。如今，它们最容易识别的语法特征是 call 和 handle 结构（或 op/perform/throw/raise 和 catch/match)。 call 是使用接口的一种构造，handle 是我们实现它们的方式。此类语言的共同思想是存在方程式（因此称为“代数”），这些方程式提供了 call 和 handle 如何以独立于界面的方式表现的基本直觉，特别是通过交互handle 顺序组合 (>>=).

在语义上，一个程序的意义可以用一棵call的树来表示，而一棵handle就是这种树的一个变换。这就是为什么 Haskell 中许多“代数效应”的化身都是从自由单子开始的，即由节点类型参数化的树类型 f:

data Free f a
  = Pure a
  | Free (f (Free f a))

从这个角度来看，程序 ex2 是一棵具有三个分支的树，标记为 7 的分支以异常结束：

ex2 :: Free ([] :+: Const Int) Int  -- The functor "Const e" models exceptions (the equivalent of "MonadError e")
ex2 = Free [Pure 5, Free (Const 7), Pure 1]
-- You can write this with do notation to look like the original ex2, I'd say "it's just notation".
-- NB: constructors for (:+:) omitted

每个效果 [] 和 Const Int 对应于某种转换树的方式，从树中消除该效果（可能引入其他效果，包括它自己）。

“捕获”异常对应于通过将 Free (Const x) 节点转换为一些新树 h x.
来处理 Const 效果
要处理 [] 效果，一种方法是使用 (>>=) 组合 Free [...] 节点的所有子节点，将它们的结果收集在最终列表中。这可以看作是深度优先搜索的推广。

根据这些转换的排序方式，您会得到 [7] 或 [5,7,1] 的结果。

当然，在 MTL 方法中存在与 monad 变换器的两个阶数的对应关系，但是程序作为树的直觉通常适用于所有代数效应，当您在在为 ListT 实现 MonadError e 等实例的过程中。这种直觉可能 a postoriori 是有意义的，但它是 a priori 混淆的，因为类型 class 实例不是 first-class 处理程序和 monad 转换器等值通常根据最终解释（隐藏在它们转换的 monad m 中）而不是初始语法来表达。

如何使用可扩展效果获得“monad 转换器的不灵活语义”？

How to get the “inflexible semantics of monad transformers” using extensible effects?

haskell

functional-programming

monads

monad-transformers

free-monad