在 filterM 中，为什么在创建所有列表后，"返回(如果 b 则 x:ys else ys)"被

Question

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

和

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

每次创建列表时是否return (if b then x:ys else ys)评估？是的，为什么结果不[[1,2,3]],[[1,2]],[[1,3]],[[1]],[[2,3]],[[2]],[[3]],[[]]？

结果是否[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]意味着在创建所有列表后return (if b then x:ys else ys)被评估一次？

Answer 1

简而言之：因为instance Monad []的绑定函数(>>=)是用concatMap实现的，而不是map。

我们可以将do块脱糖为：

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

对于m ~ []，>>=函数等价于flip concatMap，而return x等价于[x]，所以这意味着我们可以将其转换为：

filterM ::  (a -> [Bool]) -> [a] -> [[a]]
filterM p [] = [[]]
filterM p (x:xs) = concatMap (b -> concatMap (ys -> [if b then (x:ys) else ys]) (filterM p xs)) (p x)

concatMap (x -> [f x])等价于map f，因为所有这些单例列表的串联将产生一个列表，其中包含给定列表中所有元素的f结果。

因此，这意味着上述函数等效于：

filterM ::  (a -> [Bool]) -> [a] -> [[a]]
filterM p [] = [[]]
filterM p (x:xs) = concatMap (b -> map (ys -> if b then (x:ys) else ys) (filterM p xs)) (p x)

如果p是_ -> [True, False]，则意味着我们可以用[True, False]替换(p x)，从而得到：

concatMap (b -> map (ys ->if b then (x:ys) else ys) (filterM p xs)) [True, False]

这意味着concatMap是两个列表的串联：一个是bTrue，另一个是bFalse，如：

map (ys ->(x:ys)) (filterM p xs) ++ map (ys ->ys) (filterM p xs)

因此，第一个map将在filterM p xs的所有列表前面加上x，而第二个则不会。因此，上述表达式等效于：

map (x:) (filterM p xs) ++ filterM p xs

如果filterM p xs包含xs的幂集，则上面的表达式将因此包含(x:xs)的幂集。