在filterM中，为什么在创建所有列表之后对一次return（如果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

In short: because the bind function (>>=) for the instance Monad [] is implement with concatMap, not map.

We can desugar the do block as:

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))

For m ~ [], the >>= function is equivalent to flip concatMap, and return x is equivalent to [x], so that means that we can transform this, for a list, into:

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]) is equivalent to map f, since the concatenation of all these singleton lists will result in a list that contains the outcomes of f for all elements in the given list.

It thus means that the above function is equivalent to:

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)

If p is \_ -> [True, False], it thus means we can replace (p x) with [True, False], and thus obtain:

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

This thus means that concatMap is the concatenation of two lists: one where b is True, and one where b is False, like:

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

The first map will thus prepend all the lists from filterM p xs with x whereas the second one will not. The above expression is thus equivalent to:

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

if filterM p xs contains the powerset of xs, then the above expression will thus contain the powerset of (x:xs).