了解过滤器M

Question

考虑

filterM (\x -> [True, False]) [1, 2, 3]

我无法理解 Haskell 对这个 filterM 用例的魔力。该函数的源代码如下：

filterM          :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
filterM _ []     =  return []
filterM p (x:xs) =  do
    flg <- p x
    ys  <- filterM p xs
    return (if flg then x:ys else ys)

对于这个用例，p 应该是 lambda 函数 (\x -> [True, False])，第一个 x 应该是 1。那么 flg <- p x return 是什么意思呢？每次递归 flg 的值到底是多少？

Answer 1

列表单子[]模型非确定性：值列表[a]表示值[=16的多种不同可能性=].

当你在列表 monad 中看到像 flg <- p x 这样的语句时，flg 将依次采用 p x 的每个值，即 True 然后 False 在这种情况下。 filterM 的其余部分然后执行两次，每个 flg.

的值执行一次

要更详细地了解这是如何发生的，您需要了解 do 符号的脱糖和列表 monad 的 (>>=) 运算符的实现。

do 符号在对 (>>=) 运算符的调用中逐行脱糖。例如非空 filterM 案例的主体变成

p x >>= \flg -> (filterM p xs >>= \ys -> return (if flg then x:ys else ys))

这完全是机械的，因为它本质上只是将表达式前的 flg <- 替换为表达式后的 >>= \flg ->。实际上，模式匹配使这变得有点复杂，但并不复杂。

接下来是 (>>=) 的实际实现，它是 Monad 类型 class 的成员，每个实例都有不同的实现。对于[]，类型是：

(>>=) :: [a] -> (a -> [b]) -> [b]

实现类似于

[] >>= f = []
(x:xs) >>= f = f x ++ (xs >>= f)

所以循环发生在 (>>=) 的正文中。这一切都在一个库中，除了 do 符号的脱糖之外没有编译器魔法。

(>>=) 的等效定义是

 xs >>= f = concat (map f xs)

这也可以帮助您了解正在发生的事情。

对 filterM 的递归调用也会发生同样的事情：对于 flg 的每个值，都会进行递归调用并生成结果列表，最后的 return 语句针对此结果列表中的每个元素 ys 执行。

每个递归调用的 "fan-out" 在 filterM (\x -> [True, False]) [1, 2, 3] 的最终结果中产生 2^3 = 8 个元素。

Answer 2

这很简单，在我们把它全部记在纸上之后（曾经有人聪明地给出过这样的建议：不要尝试在脑子里全部做，把它全部记在纸上！）：

filterM          :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
filterM _ []     =  return []
filterM p (x:xs) =  do { flg <- p x
                       ; ys  <- filterM p xs
                       ; return (if flg then x:ys else ys) }

-- filterM (\x -> [True, False]) [1, 2, 3]
g [x,y,z] = filterM (\x -> [True, False]) (x:[y,z])
          = do {
                 flg <- (\x -> [True, False]) x
               ; ys  <- g [y,z]
               ; return ([x | flg] ++ ys) }
         = do {
                flg <- [True, False]               -- no `x` here!
              ; ys  <- do { flg2 <- (\x -> [True, False]) y
                          ; zs  <- g [z]
                          ; return ([y | flg2] ++ zs) }
              ; return ([x | flg] ++ ys) }
         = do {
                flg  <- [True, False]
              ; flg2 <- [True, False]
              ; zs   <- do { flg3 <- (\x -> [True, False]) z
                           ; s  <- g []
                           ; return ([z | flg3] ++ s) }
              ; return ([x | flg] ++ [y | flg] ++ zs) }
         = do {
                flg  <- [True, False]
              ; flg2 <- [True, False]
              ; flg3 <- [True, False]
              ; s    <- return []
              ; return ([x | flg] ++ [y | flg2] ++ [z | flg3] ++ s) }

嵌套 do 块的取消嵌套遵循 Monad 法则。

因此，在伪代码中：

    filterM (\x -> [True, False]) [1, 2, 3]
    =
      for flg in [True, False]:    -- x=1
          for flg2 in [True, False]:     -- y=2
              for flg3 in [True, False]:     -- z=3
                  yield ([1 | flg] ++ [2 | flg2] ++ [3 | flg3])

了解过滤器M

Understanding filterM

monads

haskell