跳转到内容

Haskell/Alternative 和 MonadPlus

Edit links
来自维基教科书，开放世界中的开放书籍
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（如果不存在任何 Just x）。

还应该提到，msum（可从 `Data.Foldable` 和 `Control.Monad` 中获得）只是专门针对 MonadPlus 的 asum。

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、y 和 z 的组合），其中 x^2 + y^2 == z^2 为 False。让我们看一下上面 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

请记住，guard 在其参数为 False 时返回空列表。映射跨空列表会生成空列表，无论您传递什么函数。因此，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 的组合代表树中的一条路径。应用完所有函数后，从底部开始将每个分支的结果连接在一起。任何谓词不成立的路径都会评估为空列表，因此对这种连接没有影响。

练习

[编辑 | 编辑源代码]
练习
  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、(>>=)、(>>) 等）。

与幺半群的关系

[编辑 | 编辑源代码]

在上面讨论 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 上下文相关联。

其他建议的定律

[编辑 | 编辑源代码]

注意

将其视为一个奖励部分。虽然了解这些定律的不同解释是有好处的，但总的来说，整个问题并不值得为此失眠。


除了上面几节提到的普遍假定的定律之外，还有一些其他定律从某些角度来看是有意义的，但并不适用于 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"
华夏公益教科书