单子变换器与单子堆叠有什么不同？

Question

在许多情况下，我不清楚使用转换器将两个单子合并起来是否比使用两个单独的单子更好。显然，使用两个单独的单子是麻烦的，可能会涉及到do表示法内的do表示法，但是否有一些情况下它就是表达不够充分呢？

一个例子似乎是StateT on List：组合单子不能得到正确的类型，如果你通过类似Bar（其中Bar a =（Reader r（List（Writer w（Identity a）））），获得正确的类型，它也不能做正确的事情。

但我想更全面、技术化地了解单子变换器确切带来了什么，何时需要它们，为什么需要它们。

为了使这个问题更加集中：

1. 有没有实际的单子没有相应转换器的例子（这将有助于说明变压器可以做什么，而仅仅堆叠单子无法做到）。 2. StateT和ContT是唯一的变形器，对于底层单子m（无论以哪种顺序组合），都给出了与它们组合后的类型不等价的类型吗？

（我不关心不同库的具体实现细节，而是关心单子变换器/态射作为组合效果的替代方案所添加的一般（可能与Haskell无关）问题。）

（为了提供一点背景信息，我是一名语言学家，正在用一个单子变压器栈来丰富蒙塔古语法——将单词意义组合成句子的简单类型λ演算。了解转换器是否实际上对我有用将非常有帮助。）

谢谢，

Reuben

- Reuben

---

“使用两个单独的Monad”是什么意思？你能举个例子吗？ - ErikR

好的 - List单子函子有些特别，因为任何一个表达式如果是列表，也可以作为List单子函子的一个值。试着将Writer和IO“叠加”——Writer w (IO a) 是Writer单子函子中返回IO a的一个值，并且这与 WriterT w IO a 不同——后者是在WriterT w IO单子函子中返回一个a的一个值。 - ErikR

嗯，IO 也许不是最好的例子。那 (Writer w (Maybe a)) 和 (MaybeT (Writer w) a) 呢？我认为它们是同一类型，只是互换了一下，而且行为也相同。 - Reuben

单子变换器是指对于任何单子m，类型“t m”都是一个单子“Monad”。然而，通常情况下两个单子的组合并不一定是一个单子，因此很难定义出许多抽象操作（如果有的话）来描述两个单子的组合。如果没有这些抽象操作，使用单子在Haskell中编程将会非常繁琐。大多数遇到的单子变换器都是由单子组成的组合（例如，“WriterT x m”是“Compose m (x,)”），这只是一个巧合。 - user2407038

@user2407038 我不确定大多数变压器最终看起来像组合是巧合。制作变压器的最简单方法大致是看到对于某些特定的单子，它与任何其他单子的组合将成为一个单子。我们可以使用特定单子（具有特定于该单子的实现）进行此操作，但不能对所有单子进行此操作，这基本上就是变压器的由来。你说得对，这不是“必需的”，但这不是巧合。 - Ben

Answer 1

关于Writer w (Maybe a)和MaybeT (Writer w) a之间的区别，让我们先来看一下定义：

newtype WriterT w m a = WriterT { runWriterT :: m (a, w) }
type Writer w = WriterT w Identity

newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }

使用 ~~ 表示 "结构相似"，我们有：

Writer w (Maybe a)  == WriterT w Identity (Maybe a)
                    ~~ Identity (Maybe a, w)
                    ~~ (Maybe a, w)

MaybeT (Writer w) a ~~ (Writer w) (Maybe a)
                    == Writer w (Maybe a)
                    ... same derivation as above ...
                    ~~ (Maybe a, w)

从某种角度来说，你是正确的——Writer w (Maybe a)和MaybeT (Writer w) a在结构上是相同的，它们都本质上只是一个Maybe值和一个w的组合。

区别在于我们如何将它们作为单子值处理。根据它们所属的单子不同，return和>>=类函数会执行非常不同的操作。

让我们考虑一下配对项(Just 3, []::[String])。根据我们上面得出的关联，以下是两个单子中这对配对项的表示方式：

three_W :: Writer String (Maybe Int)
three_W = return (Just 3)

three_M :: MaybeT (Writer String) Int
three_M = return 3

以下是构建空元组 (Nothing, []) 的方法：

nutin_W :: Writer String (Maybe Int)
nutin_W = return Nothing

nutin_M :: MaybeT (Writer String) Int
nutin_M = MaybeT (return Nothing)   -- could also use mzero

现在考虑这个针对一对值的函数：

add1 :: (Maybe Int, String) -> (Maybe Int, String)
add1 (Nothing, w) = (Nothing w)
add1 (Just x, w)  = (Just (x+1), w)

让我们看看如何在这两个不同的 monad 中实现它：

add1_W :: Writer String (Maybe Int) -> Writer String (Maybe Int)
add1_W e = do x <- e
             case x of
               Nothing -> return Nothing
               Just y  -> return (Just (y+1))

add1_M :: MaybeT (Writer String) Int -> MaybeT (Writer String) Int
add1_M e = do x <- e; return (e+1)
  -- also could use: fmap (+1) e

通常情况下，您会发现MaybeT单子中的代码更加简洁。

此外，从语义上讲，这两个单子非常不同...

MaybeT (Writer w) a是一个可能失败的Writer操作，并且失败会自动处理好。而Writer w (Maybe a)只是返回一个Maybe的Writer操作。如果该Maybe值最终变成了Nothing，则没有任何特殊情况发生。这在add1_W函数中得到了体现，我们必须对x进行情况分析。

选择MaybeT方法的另一个原因是，我们可以编写对任何单子栈都通用的代码。例如，如下函数：

square x = do tell ("computing the square of " ++ show x)
              return (x*x)

可以在任何具有Writer String的Monad堆栈中不变地使用，例如：

WriterT String IO
ReaderT (WriterT String Maybe)
MaybeT (Writer String)
StateT (WriterT String (ReaderT Char IO))
...

但是square的返回值不能通过Writer String (Maybe Int)进行类型检查，因为square没有返回Maybe。

当您在Writer String (Maybe Int)中编写代码时，您的代码明确显示了单子的结构，使其变得不那么通用。这是add1_W的定义：

add1_W e = do x <- e 
              return $ do 
                y <- x 
                return $ y + 1

只在双层单子栈中工作，而像 square 这样的函数则在更一般的设置中工作。

- ErikR

---

谢谢，这很有帮助。但我认为我的问题仍然存在。假设对于add1_W，您编写了以下内容： add1_W e = do x <- e return $ do y <- x return $ y + 1这仍然比add1_M麻烦，但不需要任何情况语句，并且使用了maybe和writer monads。 - Reuben

一个小修正：在 add1_M 函数中，我相信你的意思是 return (x+1)。 - Ryan

Answer 2

有没有一个实际的例子，是一个单子但没有对应的变换器（这将有助于说明变换器可以做什么，而只是堆叠单子不能做到的）。

IO 和 ST 是典型的例子。

StateT 和 ContT 是唯一给出不等价于它们与基础单子 m 的组合的类型的变换器吗（无论以哪种顺序组合）。

不是的，ListT m a 不等同于 [m a]：

newtype ListT m a =
  ListT { unListT :: m (Maybe (a, ListT m a)) }

- Daniel Wagner

---

值得注意的是，这仍然几乎是组合，只需将组合移动到固定点下方：List a = Fix (1 + a * x) 和 ListT m a = Fix (m ∘ (1 + a * x))。 - Cactus

实际上，我可能有两个看起来没有transformer的monad示例（但我不知道如何证明它们没有transformer，所以我在这里可能是错误的）。我的示例是 type C r a = Either a ((a -> r) -> r) 和 type D r a = Either a ((a -> Bool) -> Maybe a)。 - winitzki

通常，单子变换器可以分为5个不同的家族。1）在一个或另一个顺序中进行函子组合（EitherT、WriterT、ReaderT和Q a = (h a) -> a，其中h是任意的contrafunctor），2）伴随配方（StateT、ContT），3）递归配方（ListT、FreeT），4）单子的笛卡尔积，5）自由指向单子P a = Either a (m a)，其中m是另一个单子。其中，ContT不允许提升基本单子Cont r a -> ContT r a，因此不能真正被认为是完全功能的单子变换器，因此其他由Cont构建的单子也是如此。 - winitzki

@winitzki，您能否提供更多关于这个分类的阅读资源？ - Kareem Taha

@KareemTaha 我在下面的答案中添加了更多细节。 - winitzki

Answer 3

为了让这个问题更加具体化：

有没有一个单子的实际例子，没有对应的变换器（这将有助于说明变换器可以做到仅仅堆叠单子所不能做到的事情）。

只要单子是明确定义为纯的λ-演算术语，没有副作用和不使用外部库，就没有已知的缺乏变换器的单子。像IO和ST这样的Haskell单子本质上是由低级代码定义的外部库的接口。这些单子不能由纯的λ-演算定义，它们的单子变换器可能不存在。

尽管没有已知的显式单子没有变换器的例子，但也没有已知的通用方法或算法来获取给定单子的单子变换器。例如，可以定义一个任意复杂的类型构造器，结合产品、余产品和函数类型，就像在Haskell中的这段代码一样：

 type D a = Either a ((a -> Bool) -> Maybe a)

我们可以实现D的monad方法并证明monad定律成立，但是如何定义monad变换器却不那么明显。

这个D可能是一个人为制造的、人工的monad例子，但是使用该monad可能存在合法的情况，它是“在Maybe上搜索monad的自由指向monad”。

澄清一下：一个“在n上搜索monad”是类型S n q a = (a -> n q) -> n a，其中n是另一个monad，而q是一个固定的类型。

一个“在M上自由指向monad”是类型P a = Either a (M a)，其中M是另一个monad。

无论如何，我只是想说明这一点。我认为任何人都不容易想出D的monad变换器，然后证明它满足monad变换器的定律。目前还没有已知的算法可以接受任意monad代码（例如D的代码），然后生成其变换器的代码。

Monad transformer是必要的，因为堆叠两个monad并不总是一个monad。大多数“简单”的monad，如Reader、Writer、Maybe等，以特定顺序与其他monad堆叠。但是，堆叠Writer + Reader + Maybe的结果是一个更复杂的monad，不再允许与新monad堆叠。

有几个monad根本无法堆叠：State、Cont、List、Free monads、Codensity monad以及一些其他不太知名的monad，例如上面展示的“free pointed” monad。

对于每个“非堆叠”monad，都需要以某种方式猜测正确的monad transformer。

我已经研究了这个问题一段时间，并列出了创建monad transformer的技术列表，以及所有法律的完整证明。似乎没有任何系统可以为特定的monad创建monad transformer。我甚至发现了一些具有两个不等价transformer的monad。

一般而言，单子变换器可分为六个不同的家族：

1. 一个或另一个顺序的函数组合： EitherT, WriterT, ReaderT 和将 Reader 推广到一类特殊的单子，称为“刚性”单子。一个“刚性”单子的例子是 Q a = (H a) -> a，其中 H 是任意（但固定的）反变函子。

2. “伴随配方”：StateT、ContT、CodensityT、SearchT，它们提供了不可函子化的转换器。

3. “递归配方”：ListT、FreeT

4. 单子的笛卡尔积：如果 M 和 N 是单子，则它们的笛卡尔积 type P a = (M a, N a) 也是一个单子，其转换器是转换器的笛卡尔积。

5. 自由指向单子：P a = Either a (M a)，其中 M 是另一个单子。对于该单子，转换器的类型是 m (Either a (MT m a))，其中 MT 是单子 M 的转换器。

6. 单子堆栈，即通过将一个或多个单子转换器应用于其他单子而获得的单子。单子堆栈的转换器是通过使用堆栈中各个单子的所有转换器的特殊配方构建的。

可能存在一些不属于这些情况的单子，但是迄今为止我还没有看到任何例子。

有关单子转换器构造的详细信息和证明可以在我的草稿书籍https://github.com/winitzki/sofp中找到。

- winitzki

---

你可能会发现这个问题也很有趣：在Haskell中，monad transformer是否唯一？ - Daniel Wagner

@DanielWagner 谢谢。我已经在那个问题下发布了一个回答。 - winitzki