Here's a property of powersets that's easy to prove: P(A ∪ B) = {a ∪ b | a ∈ P(A), b ∈ P(B)}. In particular, if we decompose a particular set S into an element s and all the elements S' that are not s, then
P(S) = P({s} ∪ S')
= {a ∪ b | a ∈ P({s}), b ∈ P(S')}.
Now, P({s}) is small enough that we can compute it by hand: P({s}) = {{}, {s}}. Using this fact, we learn
P(S) = {a ∪ b | a ∈ {{}, {s}}, b ∈ P(S')}
= {b | b ∈ P(S')} ∪ {{s} ∪ b | b ∈ P(S')}
= P(S') ∪ {{s} ∪ b | b ∈ P(S')}
= let p = P(S') in p ∪ {{s} ∪ b | b ∈ p}
That is, one way to compute the powerset of a non-empty set is to choose an element, compute the powerset for the remainder, then either add or don't add the element to each of the subsets. The function you showed simply turns this into code, using lists as a representation of sets:
-- P ({s} ∪ S') = let p = P(S') in p ∪ {{s} ∪ b | b ∈ p}
generateSubset (x:xs) = let p = generateSubset xs in p ++ map (x:) p
The only thing left is to give a base case for the recursion, and that just comes straight from the definition of a powerset:
-- P ({}) = {{}}
generateSubset [] = [[]]
powerSet = filterM (const [False,True])
(requiresimport Control.Monad (filterM)
)powerSet = subsequences