haskell - 在filterM中，为什么 `return (if b then 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

简而言之:因为绑定(bind)函数(>>=)对于 instance Monad []用 <b>concat</b>Map 实现, 不是 map .

我们可以对 do 进行脱糖处理 block 为:

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)

A 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] ，这意味着我们可以替换 (p x)与 [True, False] , 从而得到:

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

因此这意味着 concatMap是两个列表的串联:其中 b是True , 还有一个 b是False ，比如:

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) 的幂集.