Запутано с F # List.Fold (функция powerset)

Question

Я понимаю и написал типичную функцию набора мощности в F # (аналогично разделу Алгоритмы в Википедии )

Позже я обнаружил эту реализацию powerset, которая кажетсякрасиво и компактно, ожидайте, что я не понимаю этого.

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

Я разбил это на 1-шаговую нерекурсивную функцию, чтобы найти набор мощности [1; 2], и жестко закодировал значение набора мощности2 в конце [[2];[]]

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

Вывод [[1]; []; [1; 2]; [2]], который является правильным.

Однако я ожидал, что List.Fold выведет [[1; 2]; []; [1; 2]; [2]].

Так как я былНе зная о 't', я изменил имена переменных и получил то, что ожидал.Конечно, это не правильный powerset из [1; 2].

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

Для меня 't' (тот, кто веселится, а не h :: t) - это просто имя для второго аргументав «удовольствие», но это, очевидно, не так.Так в чем же разница между написанными мной «правильными» и «неправильными» функциями F #?И что именно здесь означает «*»?

Спасибо!(Я новичок в F #)

Answer 1

В вашем "правильном" примере t изначально является именем значения, привязанного к сопоставлению с образцом, но оно скрыто параметром t в лямбда-выражении, переданном List.fold.В то время как в вашем «неправильном» примере t фиксируется как замыкание в лямбда-выражении.Я думаю, может быть, вы не намерены этот захват, вместо этого вы хотите:

//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]; []];

Answer 2

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

вот понимание / перевод на английский язык кода:

1. , если список (вы хотите включить) пуст, а затем вернуть список, который содержит пустойсписок в нем

2. , если список h::t (с заголовком h, а остальное как t, поэтому h является элементом, а t является списком).затем:

   A.(powerset t): рассчитать мощность набора t

   B.(fun xs t -> (h::t)::t::xs) означает, что вы применяете / складываете эту функцию для (powerset t).подробнее: xs - это аккумулятор, он инициализируется [].xxx::xs означает, что вы добавляете что-то к существующей мощности xs.Здесь xxx - это (h::t)::t, то есть два элемента, добавляемых к заголовку xs.(h::t) означает add head to t, а t означает каждый элемент в (powerset t).<- запутанная часть лежит в <code>t, t в (powerset t) - остальная часть списка, в то время как другая t означает элемент в (powerset t).

вот обязательный перевод функции fold:

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

Answer 3

t - переменная, связанная сопоставлением с образцом. List.fold - причудливый способ избежать явного зацикливания. А теперь иди и прочитай вводные уроки по F #.