Haskell - реализовать функцию powerset набора

Question

Я только начал изучать Haskell, и у меня были трудные времена для решения этой проблемы: powerSet :: Set a -> Set (Set a)

Вот моя попытка:

powerSet :: Tree a -> Tree (Tree a)
powerSet Empty = Empty
powerSet tree = fromList' [fromList' p | p <- powerSet' (toList tree)]

powerSet' :: [a] -> [[a]]
powerSet' [] = [[]]
powerSet' (x:xs) = [x:ps | ps <- powerSet' xs] ++ powerSet' xs

Я должен ожидать выход в такой порядок: powerset {1,2,3} => { {}, {1}, {2}, {1,2,3}, {1,3}, {2}, {2,3}, {3} }

Но вместо этого я получил это: powerset {1,2,3} => { {1,2,3}, {1,2}, {1,3}, {1}, {2,3}, {2}, {3}, {} }

Есть ли способ, которым я могу изменить это?

Answer 1

Хотите знать, есть ли способ, как я могу это изменить?

Ну, заказ { {1,2,3}, {1,2}, {1,3}, {1}, {1,3}, {2,3}, {2}, {3}, {} }, потому что именно так вы это реализовали. Действительно, для пустого списка вы возвращаете как powerSet' [], одноэлементный список с пустым списком. Для непустого списка вы выполняете рекурсивный анализ в конце списка, и сначала вы выводите этот список, где вы каждый раз добавляете x к этому списку, а затем выдает результат рекурсивного вызова без добавления.

Следовательно, для списка [2] рекурсивный регистр равен [[]], поэтому сначала мы добавляем 2, что приводит к [2], а затем мы не добавляем это, получая [].

Если мы таким образом вычислим мощность набора [1,2], рекурсивный вызов приведет к [[2], []]. Сначала мы генерируем список, в котором мы каждый раз добавляем 1, то есть [1,2] и [1], а затем мы генерируем список без добавления, делая его [2] и []. Или сложив это вместе [[1,2], [1], [2], []].

Вы можете получить результаты в другом порядке, например с помощью:

powerSet' :: [a] -> [[a]]
powerSet' l = [] : go l
    where go [] = []
          go (x:xs) = [x] : map (x:) (go xs) ++ go xs

Но, как говорит @ DanielWagner в своем комментарии :

, поэтому, возможно, это упражнение предназначено для поощрения реализации дерева поиска.

Скорее всего, вам не следует изменять порядок элементов, получаемых с помощью powerSet', но убедитесь, что ваше Tree является (двоичным) деревом поиска , и, таким образом, реализует функцию fromList таким образом, что она вставляет элементы упорядоченным образом в ваш Tree.