Confused with F# List.Fold (powerset function)

I understand and wrote a typical power set function in F# (similar to the Algorithms section in Wikipedia)

Later I found this implementation of powerset which seems nice and compact, expect that I do not understand it.

let rec powerset = function
                   | [] -> [[]]
                   | h::t -> List.fold (fun xs t -> (h::t)::t::xs) [] (powerset t);

I broke this down to a 1 step non-recursive function to find the powerset of [1;2] and hardcoded the value of power set of 2 at the end [[2]; []开发者_StackOverflow]

let right = function
                   | [] -> [[]]
                   | h::t -> List.fold (fun acc t -> (h::t)::t::acc) [] [[2]; []];

The output is [[1]; []; [1; 2]; [2]] which is correct.

However I was expecting List.Fold to output [[1; 2]; []; [1; 2]; [2]].

Since I was not certain about the 't', I modified the variable names, and I did get what I had expected. Of course this is not the correct powerset of [1;2].

let wrong  = function
                  | [] -> [[]]
                  | h::t -> List.fold (fun acc data -> (h::t)::data::acc) [] [[2]; []];

For me 't' (the one withing fun and not the h::t) is simply a name for the second argument to 'fun' but that is obviously not the case. So what is the difference in the "right" and "wrong" F# functions I have written ? And what exactly does 't' here refer to ?

Thank you ! (I am new to F#)

---

In your "right" example, t is originally the name of the value bound in the pattern match, but it is hidden by the parameter t in the lambda expression passed to List.fold. Whereas in your "wrong" example, t is captured as a closure in the lambda expression. I think maybe you don't intend this capture, instead you want:

//now it works as you expect, replaced "t" with "data" in your lambda expression.
let wrong  = function
                  | [] -> [[]]
                  | h::t -> List.fold (fun acc data -> (h::data)::data::acc) [] [[2]; []];

---

let rec powerset = function
                   | [] -> [[]]
                   | h::t -> List.fold (fun xs t -> (h::t)::t::xs) [] (powerset t);

here is the understanding/english translation of the code:

1. if the list (you want to power) is empty, then return a list, which contains an empty list in it

2. if the list is h::t (with head h and the rest as t, so h is an element and t is a list). then:

   A. (powerset t): calculate the power set of t

   B. (fun xs t -> (h::t)::t::xs) means that you apply/fold this function to the (powerset t). more details: xs is an accumulator, it is initialized to []. xxx::xs means you add something to an existing powerest xs. Here xxx is (h::t)::t, which are two elements to be added to the head of xs. (h::t) means add head to t and t means each element in (powerset t). <- the confusing part lies in t, the t in (powerset t) is the rest of the list, while the other t means an element in (powerset t).

here is an imperative translation of the fold function :

let h::t = list
let setfort = powerset t
xs <- []
foreach s in setfort do
  xs <- xs.add(t) // t is a valid subset of list
  xs <- xs.add(h::t) // t with h is also a valid subset of list

---

t is a variable bound by pattern matching. List.fold is a fancy way of avoiding explicit looping. Now, go and read some introductory tutorials about F#.