F# Powerset Function

Question

The function below returns the powerset of a set (list).

let rec powerset = function
  | [] -> [[]]
  | x::xs -> List.collect (fun sub -> [sub; x::sub]) (powerset xs)

I don't understand why exactly it works. I understand recursion. I also understand how List.collect works. I know that recursion will continue until an instance of powerset returns [[]]. However, I try to trace the returned values after that point and I never obtain the complete power set.

Answer 1

The algorithm for calculating power set goes like this:

Let's call the original set (aka "input") A. And let's pick out an item from that set, call it x. Now, powerset of A (call it P(A)) is a set of all subsets of A. We can think of all subsets of A as consisting of two groups: subsets that include x and those that don't include x. It's easy to see that subsets that don't include x are all possible subsets of A - x (A with x excluded):

  all subsets of A that don't include x = P(A-x)

How do we get all subsets of A that do include x? By taking all those that don't include x and sticking x into each one!

  all subsets of A that include x = { for each S in P(A-x) : S+x }

Now we just need to combine the two, and we get ourselves P(A):

  P(A) = P(A-x) + { for each S in P(A-x) : S+x }

This is what the last line in your code example does: it calculates P(A-x) by calling powerset xs, and then for each of those subsets, sticks an x onto it, and also includes the subset itself.