Hi BobTheCoder,

This is a very terse way of writing the function. I don't know how much you know, so I will try to be explicit, appologies if I am too explicit or not enough!

Firstly we define a new value using the let command. The values of powerset is defined as being recrusive (it calls iteslef to generate itself). It is also defined as a function which means that it implicitly takes an argument. (beacuse this is a functional language, values and functions are one and the same)

The argument to the function is a list, this is not stated but is implicitly determined. While we are at it:

Lists are a neat data structure that are also recursively defined. The first element of a list is the 'head' (which can be any type) the rest of it is the 'tail' which is a list. A new list can be made by using the cons operator (::) which joins a new element onto the front of an old list. ie 1::[4;5;6] = [1;4;5;6]. in this case, the head is '1' and the tail is [4;5;6]. The [ ; ] notation is really just a short hand for the real representation which is 1::(4::(5::(6::[]))) ... (actually, it is in other similar languages (ie Haskell) .. i'm guessing this is true in F#)

When the powerset function runs, it pattern matches the argument on one of two patterns. Either the list argument is empty ([]) in which case the function returns an empty list of lists ([[]])

1

| [] -> [[]]

Or the list not be Empty. In this case the elements are pattern matched against the pattern provided ie hd::tl which is a shorthand for getting us the head and tail.

Now the we use the function fold_left. It takes a list, a function and an initial value as arguments. It applies the function sucessivly to the list starting with the intial value and proceding from the left. So as an example:

1

let sum = fold_left (fun a b -> a + b) 0 [4;5;6] 

this would operate by applying the lambda function (a + b) as follows

1
2
3
4
5

0 + 4 = 4

4 + 5  = 9

9+ 6=  15

and thus return the value of 15 (actually we can write this as fold_left (+) 0 [4;5;6] which does the same thing but not as explicit)

Now in the case of the above code the lamda function takes two x's and tl. I'm not sure why the author chose tl for the notation because it is a little confusing. The tl inside of the lamda function only applies to that scope (insdie the brackets), the tl outside of the lamda function applies to everything not in the lamda fucntion. I will rewrite the function as follows so that the variables to not get confusing:

1
2
3

let rec powerset = function
| []->[[]]
| hd::tl->List.fold_left (fun xs ys (hd::ys)::ys::xs) [] (powerset tl);;

The fold_left applies the lambda function transform (which we will get to) to everything in the list starting with a []. However, the list is defined as a recurisve call to powerset but this time we supply only the tail of the list. So before we can calcuate the first value, we must recurse and start again, this will continue until the list supplied to poweset is empty.

Right, so let as assume that we have a list as follows [1;2]. When we run the function the following happens.

Call 1

We check if [1;2] is empty
Since it is not, we extract the head, which is '1' and the tail which is [2] and apply the fold_left function.
This tells us apply the lambda function to [] and powerset [2] since we don't know what powerset of [2] is, we recurse.

Call 2

We check if [2] is empty
Since it is not, we extract the head, which is '2' and the tail which is [] and apply the fold_left function.
This tells us apply the lambda function to [] and powerset [] since we don't know what powerset of [] is, we recurse.

Call 3

We check if [] is empty, which it is, so we return [[]] and go back to Call 2

Call 2 again

Since we now know what powerset [] is ([[]]) we apply the lamda function to [] and [[]] with hd = 2
This tells us to make form a new list which we do according to the rule and return.
... And so on. The program is written in a very terse form. I would probably write it this way to make more sense for unfamilar users:

1
2
3
4
5
6
7

#light
let rec powerset list = 
  let genSubList head xs ys = (head::ys)::ys::xs

  match list with
    | [] -> [[]]
    | head::tail -> fold_left (genSubList head) [] powerset tail

The above code should do the same thing, but makes a few concepts more explicit.

Hope this helps.

MG