了解filterM

Consider

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对于每个递归？

列表单子[] models 非决定论：值列表[a]代表了值的多种不同可能性a.

当你看到这样的声明时flg <- p x在单子列表中，flg将取每个值p x反过来，即True进而False在这种情况下。身体的其余部分filterM然后执行两次，每个值执行一次flg.

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

do符号被逐行脱糖到对(>>=)操作员。例如非空的bodyfilterM案件变成

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符号。

等效定义为(>>=) is

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

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

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

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