了解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列表中的单子,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类型类的成员,并且对每个实例具有不同的实现.对于[],类型是:

(>>=) :: [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].