Haskell/MonadPlus

我们已经学习过, Maybe 和列表都表示了一个计算能够拥有的结果数量. 换句话说, 我们使用 Maybe 来表示计算或许会失败的情况 (即0种或1种结果), 我们使用列表来表示计算能够返回0个或任意多个结果的情况.

或许有时我们会需要将两个这些类型的计算所表示的所有结果合并起来. 比如说, 我们能够将两个列表 (++) 起来以"合并"两个列表所表示的计算结果.

定义

MonadPlus 类型类定义了两个函数. mzero 是表示没有结果的值; mplus 则是一个将两个计算合并的二元函数.

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

以下是 Maybe 和列表的 instance:

instance MonadPlus [] where
  mzero = []
  mplus = (++)
 
instance MonadPlus Maybe where
  mzero                   = Nothing
  Nothing `mplus` Nothing = Nothing -- 0 个结果 + 0 个结果 = 0 个结果
  Just x  `mplus` Nothing = Just x  -- 1 个结果  + 0 个结果 = 1 个结果
  Nothing `mplus` Just x  = Just x  -- 0 个结果 + 1 个结果  = 1 个结果
  Just x  `mplus` Just y  = Just x  -- 1 个结果  + 1 个结果  = 2 个结果,
                                    -- 但是 Maybe 最多只能表示1个结果,
                                    -- 因此我们丢弃掉第二个.

另外, 在 Control.Monad.Error 模块中, (Either e) 也定义了 MonadPlus 的 instance:

instance (Error e) => MonadPlus (Either e) where
  mzero            = Left noMsg
  Left _  `mplus` n = n
  Right x `mplus` _ = Right x

和 Maybe 一样, (Either e) 表示了可能会失败的计算. 但和 Maybe 不一样的是, (Either e) 允许这个失败的计算包含一条信息 (通常是一个字符串). 一般来说, Left s 表示一个信息为 s 的失败的计算, Right x 则表示结果为 x 的成功的计算.

例子: 并行解析

传统的输入解析一般会使用一次"消耗"一个字符的一系列函数. 换句话说, 一个解析函数接收一个输入字符串, 从头部削去 (也就是所谓的"消耗") 一个满足特定条件的字符. 比如说, 一个消耗一个大写字符的函数. 但是如果这个头部的字符不满足这个特定的条件, 本次解析就失败了; 因此在这样的函数中使用 Maybe 或许是个好主意.

我们将使用 mplus 来并行运行两个解析器. 换句话说, 如果第一个解析器成功我们就返回它的结果, 否则如果第二个成功我们就返回第二个的结果. 若两个都失败了, 我们返回, Nothing.

下例中, 我们消耗一个特定的数字字符并返回它所代表的数字.

digit :: Int -> String -> Maybe Int
digit i s | i > 9 || i < 0 = Nothing
          | otherwise      = do
  let (c:_) = s
  if [c] == show i then Just i else Nothing

我们的 guard 保证了我们所检查的 Int只有一位. 然后, 我们检查字符串的首位是否匹配我们所想要的数字. 如果匹配的话, 我们返回一个包裹在 Just 中的数字. do 代码块保证了失败的任何模式匹配都将返回 Nothing.

我们使用 digit 和 mplus 函数来解析一个由二进制位组成的字符串:

binChar :: String -> Maybe Int
binChar s = digit 0 s `mplus` digit 1 s

解析器库一般都以类似的方式使用 MonadPlus. 好奇的话, 你可以看看 Text.ParserCombinators.ReadP 中 (+++) 函数的实现, 或者 Text.ParserCombinators.Parsec.Prim 中的 (<|>).

MonadPlus 法则

MonadPlus 的 instance 必须满足一些法则, 就如同 Monad 的 instance 需要满足三条 Monad 法则一样. 不幸的是, 人们对 MonadPlus 法则并没有达成一致的意见. 最通常的意见是, mzero 和 mplus 需要形成一个幺半群 (monoid). 换句话说:

-- mzero 是一个无具体意义的"中立"值
mzero `mplus` m  =  m
m `mplus` mzero  =  m
-- mplus 满足结合律
-- (但并不是所有的 instance 都满足这条定律, 因为这和一些无尽的值构造相悖)
m `mplus` (n `mplus` o)  =  (m `mplus` n) `mplus` o

"形成一个幺半群" 并没有什么特别之处: 在上例中, "中立值" 和 "结合律" 可以比作整数加法的交换律和整数0. 事实上, 这也是为什么这两个函数叫做 mzero (m零) 和 mplus (m加).

Control.Monad 的 Haddock 文档 额外规定了以下法则:

mzero >>= f  =  mzero
m >> mzero   =  mzero

HaskellWiki 则给出了具有争议的另一条:

(m `mplus` n) >>= k  =  (m >>= k) `mplus` (n >>= k)

甚至还有更多的法则. 有时例如 IO 的 Monad 也会有 MonadPlus 的 instance. 参见 All About Monads 以及 Haskell Wiki.

实用函数

除了基础的 mplus 和 mzero, 还有两个应用了 MonadPlus 的通用函数:

msum

处理 MonadPlus 的常见操作: 将一个列表中的 MonadPlus 值, 例如 [Maybe a] 或 [[a]], 用 mplus 进行 fold. msum 函数正是为此而生:

msum :: MonadPlus m => [m a] -> m a
msum = foldr mplus mzero

某种意义上, msum 是只能用在列表上的函数 concat 的推广. 事实上, 当应用在列表上时这两个函数完全相同. 对于 Maybe, msum 返回其中的第一个 Just x,若其不存在则返回 Nothing.

guard

我们注意到, 列表 monad 和列表解析之间的惊人相似, 但我们或许不是很清楚列表解析中的过滤是如何实现的. guard 就是实现的方式.

我们来看看这个计算所有勾股数 (也就是能形成直角三角形三边长的三个数) 的列表解析. 首先我们检查暴力的方法. 我们用一个布尔条件来过滤那些非勾股数的组合:

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

将如上的列表解析写成列表 monad 的形式:

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

guard 函数的定义:

guard :: MonadPlus m => Bool -> m ()
guard True  = return ()
guard _ = mzero

具体地, 当它获得一个 False 作为参数时, guard 会将整个 do 代码块的运算结果化为 mzero. 因为由于 MonadPlus 法则第一条, mzero 位于 (>>=) 左侧的运算将总是得回 mzero. do 代码块实际上是一系列用 (>>=) 串联起来的表达式的语法糖, 因此在任何位置出现的 mzero 都将使它的最终结果变为 mzero.

我们将扩展上面的 pythags 函数以展示 guard 在列表 monad 中的应用. 首先, 这是将 guard 特化到列表 monad 后的实现:

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

简单地说, guard 堵住了 一条运算路径. 在 pythags 中, 我们希望能够堵住所有 x^2 + y^2 == z^2 为 False 的路径 (或者说, x, y 和 z 的组合). 让我们在展开 do 代码块后的代码:

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

将 (>>=) 和 return 替换成它们在列表 monad 中的特化 (并使用 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 返回一个空列表. 而无论我们使用什么函数, 对一个空列表 map 总是返回一个空列表. 因此在 gd 的 let 绑定中对于 guard 的调用中返回的空列表将使 gd 返回一个空列表, 因此 ret 也是一个空列表.

为了更好地理解, 我们可以将列表 monad 中的计算想象成一棵树. 用我们的算法, 我们需要从顶部开始为每一个 x 的选取创建一个分支, 然后再在这些分支地下为所有 y 的选择创建分支, z 也是同样. 因此这棵"计算树"会长这样:

   start
   |____________________________________________ ...
   |                     |                    |
x  1                     2                    3
   |_______________ ...  |_______________ ... |_______________ ...
   |      |      |       |      |      |      |      |      |
y  1      2      3       2      3      4      3      4      5
   |___...|___...|___... |___...|___...|___...|___...|___...|___...
   | | |  | | |  | | |   | | |  | | |  | | |  | | |  | | |  | | |
z  1 2 3  2 3 4  3 4 5   2 3 4  3 4 5  4 5 6  3 4 5  4 5 6  5 6 7

每一个 x, y 和 z 的组合都代表了树中的一条路径. 当所有计算完成以后, 每一个分支被从下至上合并起来. 任何不满足条件的路径此时被转化成空列表, 因此对合并过程没有影响.

练习
证明 Maybe 和列表确实满足 MonadPlus 法则. 我们能够修改上面的解析器, 使其接收任意字符: -- | 消耗输入中的一个指定字符, 返回一个二元组, 其中包含了这个字符以及余下的字符串. 我们用 一个 do 代码块使得任意位置失败的模式匹配 都将返回 Maybe 的"失败状态" (也就是 Nothing) char :: Char -> String -> Maybe (Char, String) char c s = do let (c':s') = s if c == c' then Just (c, s') else Nothing 此时我们能够实现一个 hexChar 函数, 其接收任何合法的十六进制数字符 (0-9 或 a-f). 试着实现这个函数 (提示: map digit [0..9] :: [String -> Maybe Int]).

和 Monoid 的关系

当我们讨论 MonadPlus 法则时, 我们提到了数学上的幺半群 (Monoid). 事实上 Haskell 中存在着一个 Monoid 类型类, 详细教程请参见Haskell趣学指南中的章节:

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

列表是一个简单的 monoid:

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

看起来是不是很熟悉呢? 尽管和 MonadPlus 有些相似, 它们有一点关键而微妙的区别. 注意在 instance 声明中我们使用了 [a] 而不是 []. Monoid 并不一定是其他类型的"容器", 或者说不一定是多态的. 比如说, 整数加法构成了一个 Monoid, 其中"中立值" (mempty) 为0.

确实, MonadPlus 的 instance 看起来和 Monoid 类似, 因为两者都有"零"和"加"的概念. 事实上, 我们能够让 MonadPlus 成为 Monoid 的子类 (如果值得这番功夫的话):

 instance MonadPlus m => Monoid (m a) where
   mempty  = mzero
   mappend = mplus

注解 由于 instance 声明中自由变量 a 的存在, 上述代码在 Haskell 98 中并不合法. 除非你开启 GHC 的 语言扩展 FlexibleInstances: 如果你使用的是 GHCi, 使用参数 -XFlexibleInstances 启动它或者在交互提示符下输入 :set -XFlexibleInstances. 如果你编译后再运行程序的话, 在源文件第一行加上 {-# LANGUAGE FlexibleInstances #-}.

我们重申一下, Monoid 和 MonadPlus 工作与不同的"层次". 正如之前所说, Monoid 并不一定是其他类型的"容器", 或者说不一定是多态的. 更加正式地, Monoid 的 kind 为 *, 但 MonadPlus 的 instance 的 kind 为 * -> *. (后者本身也是 Monad).

---

MonadPlus

习题解答

Monads

理解 Monad  >> 高级 Monad  >> Monad 进阶  >> MonadPlus  >> Monadic parser combinators  >> Monad transformers  >> Monad 实务

Haskell

Haskell基础 >> 初级Haskell >> Haskell进阶 >> Monads 高级Haskell >> 类型的乐趣 >> 理论提升 >> Haskell性能 库参考 >> 普通实务 >> 特殊任务