Power sets

I was browsing through the IRC logs on #haskell when I came upon this expression for defining a power-set: powerset = filterM (const [True, False]). This piqued my interest, and soon I had a little puzzle on hand. Let's take a look at how this works.

> powerset = filterM (const [True, False])
> powerset []
[[]]
> powerset [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

For those of you who don't know what a power set is, it's basically a set that comprises of all the possible subsets of given set. For a given set S, the power set is defined as

\(P(S) \colon= \text{ T | Set(T), T $\subset$ S} \)

including the empty set \(\emptyset\) and S itself. I started with filterM and drilled downwards from there:

filterM :: (Applicative m) => (a -> m Bool) -> [a] -> m [a]
filterM p
  = foldr (\ x -> liftA2 (\ flg -> if flg then (x:) else id) (p x)) (pure [])

liftA2 :: (a -> b -> c) -> f a -> f b -> f c
liftA2 f x = (<*>) (fmap f x)

liftA2 lifts the lambda function \flg -> if flg then (x:) else id into [True, False], which produces a list of functions. If we take a collection of integers as an example, then each call produces the following

-- As an example, given [1, 2 ,3], calling liftA2 with the first value 1
-- liftA2 = (<*>) (fmap f x)
--        = (<*>) [(1:), id] :: Num a => [[a]] -> [[a]]
-- gives us a list of 2 actions that has the shape
-- [append x, do nothing]

-- Let's name each of these
> let g1 = (<*>) [(1:), id]
> let g2 = (<*>) [(2:), id]
> let g3 = (<*>) [(3:), id]

-- `pure` [] simply evaluates to [[]] here
-- If we fold the above from right to left
> g1 (g2 (g3 [[]]))
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
> g1 (g2 (g3 [[]])) == powerset [1,2,3]
True

And that's how this magical expression really works underneath!