Блог

Я понял и написал типичную функцию набора мощности в 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]] который является правильным.

Однако я ожидал список.Сворачивание для вывода [[1; 2]; []; [1; 2]; [2]] .

Поскольку я не был уверен насчет ‘t’, я изменил имена переменных и получил то, что ожидал. Конечно, это неправильный набор мощности для [1; 2].

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

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

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

В вашем «правильном» примере, 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]; []];
  

 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 означает, что вы добавляете что-то к существующему powerest xs . Вот xxx это (h::t)::t , какие два элемента нужно добавить в заголовок xs . (h::t) означает add head to t и t означает каждый элемент в (powerset t) . <- запутанная часть заключается в 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
  

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