F # Функция Powerset

Question

Функция ниже возвращает набор параметров набора (списка).

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

Я не понимаю, почему именно это работает. Я понимаю рекурсию. Я также понимаю, как работает List.collect. Я знаю, что рекурсия будет продолжаться до тех пор, пока не вернется экземпляр powerset [[]]. Тем не менее, я пытаюсь отслеживать возвращаемые значения после этой точки, и я никогда не получаю полный набор мощности.

Answer 1

Алгоритм расчета набора мощности выглядит следующим образом:

Назовём исходный набор (так называемый «вход») A. И давайте выберем элемент из этого набора, назовите его x. Теперь, poweret A (назовите его P(A)) представляет собой набор всех подмножеств A. Мы можем думать обо всех подмножествах A как состоящих из двух групп: подмножеств, которые включают x и те, которые не включают x. Легко видеть, что подмножества, которые не включают в себя x все возможные подмножества A - x (A с x исключенные):

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

Как мы получаем все подмножества A что делать включают x? Принимая все те, которые не включают x и вставляют x в каждый!

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

Теперь нам нужно объединить два, и мы получим себе P(A):

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

Это то, что последняя строка в вашем примере кода делает: он вычисляет P(A-x) по телефону powerset xs, а затем для каждого из этих подмножеств, накладывает на него x, а также включает в себя подмножество.