跳转到内容

Haskell/Alternative 和 MonadPlus

Edit links
来自 Wikibooks，开放世界的开放书籍
< Haskell
(重定向自 Haskell/MonadPlus)
Alternative 和 MonadPlus (解答)
单子

序言：IO，一个应用函子
理解单子
Maybe
List
do 符号
IO
State
Alternative 和 MonadPlus
单子转换器

在我们的学习中，我们看到 Maybe 和列表都可以表示结果数量不同的计算。我们使用 Maybe 来表示计算可能会以某种方式失败（也就是说，它可能会有零个结果或一个结果），而我们使用列表来表示可能有多个可能结果的计算（范围从零到任意多个结果）。在这两种情况下，一个有用的操作是将多个计算的所有可能结果合并成一个计算。例如，对于列表，这将相当于连接可能结果的列表。Alternative 类以通用方式捕获此合并。

定义

[编辑 | 编辑源代码]

注意

Alternative 类及其方法可以在 Control.Applicative 模块中找到。


Alternative 是 Applicative 的一个子类，其实例必须至少定义以下两个方法

class Applicative f => Alternative f where
  empty :: f a
  (<|>) :: f a -> f a -> f a

empty 是一个具有零个结果的应用计算，而 (<|>) 是一个将两个计算组合起来的二元函数。

以下是 Maybe 和列表的两个实例定义

instance Alternative Maybe where
  empty               = Nothing
  -- Note that this could have been written more compactly.
  Nothing <|> Nothing = Nothing -- 0 results + 0 results = 0 results
  Just x  <|> Nothing = Just x  -- 1 result  + 0 results = 1 result
  Nothing <|> Just x  = Just x  -- 0 results + 1 result  = 1 result
  Just x  <|> Just y  = Just x  -- 1 result  + 1 result  = 1 result:
                                -- Maybe can only hold up to one result,
                                -- so we discard the second one.

instance Alternative [] where
  empty = []
  (<|>) = (++) -- length xs + length ys = length (xs ++ ys)

示例：并行解析

[编辑 | 编辑源代码]

传统的输入解析涉及一次消费一个字符的输入的函数。也就是说，解析函数接收一个输入字符串，如果字符满足某些条件，就会从字符串的开头截取（即“消费”）字符。例如，你可以编写一个函数来消费一个大写字母。如果字符串开头的字符不满足给定条件，则解析器已失败。例如，在下面的示例中，我们消费输入中的一个数字并返回已解析的数字。失败的可能性通过使用 Maybe 来表示。

digit i (c:_)
  | i > 9 || i < 0 = Nothing
  | otherwise      =
    if [c] == show i then Just i else Nothing

守卫确保我们正在检查的 Int 是一个单一位数。否则，我们只是检查我们的字符串的第一个字符是否与我们正在检查的数字匹配。如果通过，我们返回用 Just 包裹的数字。否则我们返回 Nothing。

现在，(<|>) 可以用来并行运行两个解析器。也就是说，如果第一个解析器成功，我们就使用它的结果，否则我们就使用第二个解析器的结果。如果两者都失败，则组合的解析器返回 Nothing。我们可以使用 digit 和 (<|>) 来例如解析二进制数字字符串

binChar :: String -> Maybe Int
binChar s = digit 0 s <|> digit 1 s

解析器库通常以这种方式使用 Alternative。两个例子是 Text.ParserCombinators.ReadP 中的 (+++) 和 Text.ParserCombinators.Parsec.Prim 中的 (<|>)。这种使用模式可以用选择来描述。例如，如果我们想给 binChar 一个可以成功解析的字符串，我们有两个选择：要么以 '0' 开始字符串，要么以 '1' 开始字符串。

MonadPlus

[编辑 | 编辑源代码]

MonadPlus 类与 Alternative 密切相关

class Monad m => MonadPlus m where
  mzero :: m a
  mplus :: m a -> m a -> m a

它的定义与 Alternative 相同，除了方法名称不同，Applicative 约束被改为 Monad。不出所料，对于既有 Alternative 又有 MonadPlus 实例的类型，mzero 和 mplus 应该分别等效于 empty 和 (<|>)。

人们可能会合理地怀疑为什么存在看似多余的 MonadPlus 类。部分原因是历史原因：就像 Monad 在 Haskell 中比 Applicative 早出现很久一样，MonadPlus 也比 Alternative 早得多。除了这种偶然之外，还有一些额外的期望（这些期望不适用于 Alternative）关于 MonadPlus 方法应该如何与 Monad 相互作用，因此表明某物是 MonadPlus 是一个比表明它既是 Alternative 又是 Monad 更强的断言。在本章的后面，我们将对这个问题做一些额外的考虑。

Alternative 和 MonadPlus 法则

[编辑 | 编辑源代码]

就像大多数通用类一样，Alternative 和 MonadPlus 预计会遵循一些法则。然而，对于法则的完整集合应该是什么，并没有达成普遍共识。最常采用的法则，也是为 Alternative 提供直觉最关键的法则，说明 empty 和 (<|>) 构成一个幺半群。这意味着

-- empty is a neutral element
empty <|> u  =  u
u <|> empty  =  u
-- (<|>) is associative
u <|> (v <|> w)  =  (u <|> v) <|> w

关于“构成一个幺半群”没有什么花哨的地方：在上面，“中性元素”和“结合律”就像整数的加法被认为是结合律的，并且具有零作为其中性元素一样。事实上，这个类比是 MonadPlus 方法名称 mzero 和 mplus 的来源。

至于 MonadPlus，至少通常会有幺半群法则，它们与上面提到的法则完全对应...

mzero `mplus` m  =  m
m `mplus` mzero  =  m
m `mplus` (n `mplus` o)  =  (m `mplus` n) `mplus` o

... 以及另外两个法则，由 Control.Monad 文档引用

mzero >>= f  =  mzero -- left zero
m >> mzero   =  mzero -- right zero

如果 mzero 被解释为失败的计算，这些法则表明，在单子计算链中的失败会导致整个链的失败。

我们将在本章末尾讨论一些关于 Alternative 和 MonadPlus 的其他法则建议。

有用函数

[编辑 | 编辑源代码]

除了 (<|>) 和 empty 之外，基础库中还有另外两个与 Alternative 相关的通用函数。

asum

[编辑 | 编辑源代码]

使用 Alternative 时，一个常见的任务是取一个备选值的列表，例如 [Maybe a] 或 [[a]]，并使用 (<|>) 将其折叠起来。来自 Data.Foldable 的函数 asum 实现了这个作用

asum :: (Alternative f, Foldable t) => t (f a) -> f a
asum = foldr (<|>) empty

在某种意义上，asum 概括了特定于列表的 concat 操作。事实上，当列表是正在使用的 Alternative 时，这两者是等效的。对于 Maybe，asum 会找到列表中的第一个 Just x，如果没有就返回 Nothing。

还应该提到的是，msum 可用于 `Data.Foldable` 和 `Control.Monad`，只是 asum 专门用于 MonadPlus。

msum :: (MonadPlus m, Foldable t) => t (m a) -> m a

guard

[编辑 | 编辑源代码]

当讨论列表单子时，我们注意到它与列表推导非常相似，但我们没有讨论如何镜像列表推导过滤。Control.Monad 中的 guard 函数允许我们做到这一点。

考虑以下推导，它检索所有毕达哥拉斯三元组（即作为直角三角形边长的三个整数）。首先，我们将检查暴力方法。我们将使用布尔条件进行过滤；即毕达哥拉斯定理

pythags = [ (x, y, z) | z <- [1..], x <- [1..z], y <- [x..z], x^2 + y^2 == z^2 ]

将上面的推导转换为列表单子 do-block 是

pythags = do
  z <- [1..]
  x <- [1..z]
  y <- [x..z]
  guard (x^2 + y^2 == z^2)
  return (x, y, z)

guard 函数可以为所有 Alternative 定义如下

guard :: Alternative m => Bool -> m ()
guard True  = pure ()
guard _ = empty

如果 guard 的谓词为 False，它将减少 do-block 为 empty。给定左零律...

mzero >>= f = mzero
-- Or, equivalently:
empty >>= f = empty

... >>= 操作左侧的 empty 将再次产生 empty。由于 do-block 被分解为许多通过 (>>=) 连接的表达式，任何位置的 empty 将导致整个 do-block 变成 empty。

让我们详细检查 guard 在 pythags 中的作用。首先，以下是 guard 为列表单子定义的

-- guard :: Bool -> [()]
guard True  = [()]
guard _ = []

基本上，guard 封锁 一条路径。在 pythags 中，我们想要封锁所有 x^2 + y^2 == z^2 为 False 的路径（或 x、y 和 z 的组合）。让我们看看上面 do-block 的展开以了解它的工作原理

pythags =
  [1..] >>= \z ->
  [1..z] >>= \x ->
  [x..z] >>= \y ->
  guard (x^2 + y^2 == z^2) >>= \_ ->
  return (x, y, z)

将 >>= 和 return 替换为它们在列表单子中的定义（并使用一些 let 绑定以保持可读性），我们得到

pythags =
 let ret x y z = [(x, y, z)]
     gd  z x y = concatMap (\_ -> ret x y z) (guard $ x^2 + y^2 == z^2)
     doY z x   = concatMap (gd  z x) [x..z]
     doX z     = concatMap (doY z  ) [1..z]
     doZ       = concatMap (doX    ) [1..]
 in doZ

请记住，如果参数为 False，guard 会返回空列表。映射到空列表会生成空列表，无论你传递什么函数。因此，在 gd 中对 guard 的调用产生的空列表将导致 gd 生成空列表，而 \_ -> ret x y z 在其他情况下会添加结果，但实际上并没有被调用。

为了理解这为什么重要，请将列表计算视为一棵树。使用我们的毕达哥拉斯三元组算法，我们需要从顶部开始为 z 的每一个选择创建一个分支，然后从这些分支中的每一个分支开始为 x 的每一个值创建一个分支，然后从这些分支中的每一个分支开始为 y 的每一个值创建一个分支。因此，树看起来像这样

   start
   |_________________________...
   |    |         |
z  1    2         3
   |    |____     |____________
   |    |    |    |       |    |
x  1    1    2    1       2    3
   |    |_   |    |___    |_   |
   |    | |  |    | | |   | |  |
y  1    1 2  2    1 2 3   2 3  3

z、x 和 y 的每一个组合表示树中的一条路径。一旦所有函数都应用完成，每个分支的结果将从底部开始连接在一起。任何谓词不成立的路径都会评估为空列表，因此对这种连接没有影响。

练习

[edit | edit source]
练习
  1. 证明 Maybe 和列表的 Alternative 单子定律。
  2. 我们可以增强来自并行解析示例的解析器，使其能够以以下方式处理任何字符
    -- | Consume a given character in the input, and return 
--   the character we just consumed, paired with rest of 
--   the string. We use a do-block  so that if the
--   pattern match fails at any point, 'fail' of the
--   Maybe monad (i.e. Nothing) is returned.
char :: Char -> String -> Maybe (Char, String)
char c s = do
  c' : s' <- return s
  guard (c == c')
  return (c, s')
    然后就可以编写一个 hexChar 函数来解析任何有效的十六进制字符（0-9 或 a-f）。尝试编写此函数（提示：map digit [0..9] :: [String -> Maybe Int]）。
  3. 使用 guard 和 Applicative 组合器（pure、(<*>)、(*>) 等）从Maybe 单子章节实现 safeLog。不要使用 Monad 组合器（return、(>>=)、(>>) 等）。

与单子的关系

[edit | edit source]

在讨论上面的 Alternative 定律时，我们提到了单子的数学概念。事实上，Haskell 中已经有一个 Monoid 类（在Data.Monoid 中定义）。单子的完整介绍将在后面的章节中给出。但是现在，只需要说 Monoid 的最小定义实现了两种方法；即中性元素（或“零”）和关联二元运算（或“加”）。

class Monoid m where 
  mempty  :: m
  mappend :: m -> m -> m

例如，列表形成一个简单的单子

instance Monoid [a] where
  mempty  = []
  mappend = (++)

看起来很熟悉，不是吗？尽管与 Alternative 和 MonadPlus 有惊人的相似之处，但有一个关键的区别。请注意实例声明中使用的是 [a] 而不是 []。单子不一定是任何东西的“包装器”，或者参数多态的。例如，整数在加法下形成一个单子，其中 0 作为中性元素。Alternative 是一个独立的类型类，因为它捕获了一种特定类型的单子，具有独特的属性 - 例如，一个二元运算(<|>) :: Alternative f => f a -> f a -> f a，它本质上与 Applicative 上下文相关联。

其他建议的定律

[edit | edit source]

注意

将此视为奖励部分。虽然了解这些定律的不同版本是件好事，但总的来说，这个问题不值得为此而失眠。


除了上面几节中提到的普遍假定的定律之外，还有一些其他定律从某些角度来看是有意义的，但并不适用于 Alternative 和 MonadPlus 的所有现有实例。特别是目前的 MonadPlus 可能被视为几个假设类的交集，这些类将具有其他定律。

以下两个附加定律通常被建议用于 Alternative。虽然它们确实适用于 Maybe 和列表，但核心库中存在反例。还要注意，对于也是 MonadPlus 的 Alternative，前面提到的 mzero 定律并不是这些定律的结果。

(f <|> g) <*> a = (f <*> a) <|> (g <*> a) -- right distributivity (of <*>)
empty <*> a = empty -- right absorption (for <*>)

至于 MonadPlus，一个常见的建议是左分配定律，它适用于列表，但不适用于 Maybe

(m `mplus` n) >>= k  =  (m >>= k) `mplus` (n >>= k) -- left distribution

相反，左捕获定律适用于 Maybe，但不适用于列表

return x `mplus` m = return x -- left catch

通常假定任何 MonadPlus 实例都会满足左分配或左捕获。为什么不能两者都满足呢？假设它们都满足。那么对于任何 x, y :: m a，

x `mplus` y
= -- monad identity
(return x >>= id) `mplus` (return y >>= id)
= -- left distribution
(return x `mplus` return y) >>= id
= -- left catch
return x >>= id
= -- monad identity
x

这立即排除了除最琐碎的 MonadPlus 实现之外的所有实现。更糟糕的是，这意味着对于任何 x，mzero `mplus` x = mzero。然后添加单子标识定律 mzero `mplus` x = x 意味着该单子只有一个值，因此与琐碎的单子 Data.Proxy.Proxy 同构。

最后，值得注意的是，即使关于单子定律也存在分歧。有时针对它们提出的一个案例是，对于某些通常用 MonadPlus 表示的非确定性单子，关键定律是左零和左分配，而在这些情况下，单子定律会导致困难，应该完全放松或放弃。

一些完全可选的进一步阅读，供好奇的读者参考


检索自 "https://wikibooks.cn/w/index.php?title=Haskell/Alternative_and_MonadPlus&oldid=4342264"
华夏公益教科书