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 的组合都代表了树中的一条路径. 当所有计算完成以后, 每一个分支被从下至上合并起来. 任何不满足条件的路径此时被转化成空列表, 因此对合并过程没有影响.
练习 |
---|
|
和 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 声明中自由变量
|
我们重申一下, 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
|