Приведенная ниже функция возвращает мощность набора (списка).
let rec powerset = function
| [] -> [[]]
| x::xs -> List.collect (fun sub -> [sub; x::sub]) (powerset xs)
Я не понимаю, почему именно это работает. Я понимаю рекурсию. Я также понимаю, как работает List.collect. Я знаю, что рекурсия будет продолжаться до тех пор, пока экземпляр powerset не вернет [[]]. Однако я пытаюсь отследить возвращенные значения после этой точки и никогда не получаю полный набор мощности.
Алгоритм расчета набора мощности выглядит следующим образом:
Назовем исходный набор (он же «вход») A. И давайте выберем предмет из этого набора, назовем его x. Теперь набор мощности 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, а также включает само подмножество.
