haskell - 了解filterM

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 是什么呢？返回？ flg 的值到底是多少？对于每个递归？

Answer 1

列表单子(monad) []模型非确定性:值列表 [a]代表 a 值的多种不同可能性.

当您看到类似 flg <- p x 的语句时在单子(monad)列表中，flg将采用 p x 的每个值依次，即True然后False在这种情况下。 filterM 的其余部分然后执行两次，对 flg 的每个值执行一次.

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

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

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

这完全是机械的，因为它本质上只是替换 flg <-在 >>= \flg -> 表达式之前表达后。实际上，模式匹配使事情变得更复杂一些，但也不是太复杂。

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

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

其实现类似于

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

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

(>>=) 的等效定义是

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

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

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

每次递归调用的这种“扇出”都会导致 2^3 = 8最终结果 filterM (\x -> [True, False]) [1, 2, 3] 中的元素.