How is this power set generating function working

Question

While trying to generate power set for a given list, I came across this function over the internet. There was no explanation, but testing suggests that it seems to work correctly. I am not able to understand how this function is working. I will be thankful for any such explanations.

generateSubset [] = [[]]
generateSubset (x:xs) = let p = generateSubset xs in p ++ map (x:) p

Answer 1

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 []  = [[]]

Answer 2

The code you gave uses a lot of Haskell's syntactic sugar. (As others have already covered the semantics, I'll omit that.) Here's the main syntax I noticed in the code:

• lack of type annotations. Haskell uses type inference, which makes type annotations optional (but recommended). Use GHCi to determine the type:

  *Main> :t generateSubset
  generateSubset :: [a] -> [[a]]
  

• pattern matching. See LYAH for a nice introduction.

• let expressions. Again, see LYAH.

• partial application -- (x:). LYAH for the win!

• operator sections -- (x:) again. This allows for partial application of an infix function (in this case, :). It's the same as:

  myCons :: a -> [a] -> [a]
  myCons e es = e : es
  
  myPartial :: [a] -> [a]
  myPartial = myCons x -- partial application
  

• use of function/operator precedences -- p ++ map (x:) p. This is parsed as (p) ++ (map (x:) p), because function application always has higher precedence than infix operator application.