powerset :: [a] -> [[a]]
powerset xs = filterM (\x -> [True, False]) xs
------------- -----
filterM :: Monad m => (a -> m Bool ) -> [a] -> m [a]
-- filter :: (a -> Bool ) -> [a] -> [a] (just for comparison)
------------- -----
m Bool ~ [Bool] m ~ []
So this is filter
"in" the nondeterminism (list) monad.
Normally, filter keeps only those elements in its input list for which the predicate holds.
Nondeterministically, we get all the possibilities of keeping the elements for which the nondeterministic predicate might hold, and removing those for which it might not hold. Here, it is so for any element, so we get all the possibilities of keeping, or removing, an element.
Which is a powerset.
Another example (in a different monad), building on the one in Brent Yorgey's blog post mentioned in the comments,
>> filterM (\x-> if even x then Just True else Nothing) [2,4..8]
Just [2,4,6,8]
>> filterM (\x-> if even x then Just True else Nothing) [2..8]
Nothing
>> filterM (\x-> if even x then Just True else Just False) [2..8]
Just [2,4,6,8]
Let's see how this is actually achieved, with code. We'll define
filter_M :: Monad m => (a -> m Bool) -> [a] -> m [a]
filter_M p [] = return []
filter_M p (x:xs) = p x >>= (\b ->
if b
then filter_M p xs >>= (return . (x:))
else filter_M p xs )
Writing out the list monad's definitions for return
and bind (>>=
) (i.e. return x = [x]
, xs >>= f = concatMap f xs
), this becomes
filter_L :: (a -> [Bool]) -> [a] -> [[a]]
filter_L p [] = [[]]
filter_L p (x:xs) -- = (`concatMap` p x) (\b->
-- (if b then map (x:) else id) $ filter_L p xs )
-- which is semantically the same as
-- map (if b then (x:) else id) $ ...
= [ if b then x:r else r | b <- p x, r <- filter_L p xs ]
Hence,
-- powerset = filter_L (\_ -> [True, False])
-- filter_L :: (a -> [Bool] ) -> [a] -> [[a]]
powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs)
= [ if b then x:r else r | b <- (\_ -> [True, False]) x, r <- powerset xs ]
= [ if b then x:r else r | b <- [True, False], r <- powerset xs ]
= map (x:) (powerset xs) ++ powerset xs -- (1)
-- or, with different ordering of the results:
= [ if b then x:r else r | r <- powerset xs, b <- [True, False] ]
= powerset xs >>= (\r-> [True,False] >>= (\b-> [x:r|b] ++ [r|not b]))
= powerset xs >>= (\r-> [x:r,r])
= concatMap (\r-> [x:r,r]) (powerset xs) -- (2)
= concat [ [x:r,r] | r <- powerset xs ]
= [ s | r <- powerset xs, s <- [x:r,r] ]
and we have thus derived the two usual implementations of powerset
function.
The flipped order of processing is made possible by the fact that the predicate is constant (const [True, False]
). Otherwise the test would be evaluated over and over again for the same input value, and we probably wouldn't want that.
m
in this example? What doesfilterM
turn into if you expand the monadic operations?filterM
now.