Powersets in Haskell

powerset.hs

powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs) = map (x:) (powerset xs) ++ powerset xs

Powerset always twists my head... and I just came across your gist and this nice version, in case you haven't seen it:

powerset :: [a] -> [[a]]
powerset = filterM (const [True, False])

@chrisbloecker Internally filterM is doing something very similar to what @angerman's version is doing. The True and False are the 2 cases. A list monad essentially represents non-determinism, and hence it takes all the cases. So here [True,False], filterM will happen for both True as well as False. When the predicate is True it takes the first branch (map (x:) (powerset xs) ) and when it is False it takes the second branch powerset xs.

It is quite simple to grok if you observe 2 things:

1. The bind instance of List monad
2. The definition of the filterM function