Haskell - powerset Комплекта - PullRequest
Новая
       6

Haskell - powerset Комплекта

0 голосов
/ 09 января 2020

Я новичок в Haskell.

Я реализовал набор в виде двоичного дерева 

Set a = Node a | Tree a (Set a) (Set a)

Я застрял при создании функции полномочий. Любые идеи о том, как я мог бы реализовать функцию powerset, в идеале не совсем то же самое, что Data.Set ??

1 Ответ

1 голос
/ 09 января 2020

Давайте рассмотрим более простую версию powerset, которая использует списки: 

powerset [] = [[]]
powerset (x:xs) = [x:ps | ps <- pxs] ++ pxs where
   pxs = powerset xs

Запуск powerset [1, 2, 3] Выход [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

Из этого вы можете увидеть основные c функции и данные Определения, необходимые для реализации операций с BST:

  1. powerset [] = [[]] пустой набор, который отсутствует в вашем случае, как указано в комментариях
  2. x:ps способ добавить элемент к набору
  3. И, более тонкий: удаление элемента из набора, потому что (x:xs) разбивает множество int x и xs, которое используется в pxs = powerset xs

Простая реализация выглядела бы так: 

data TreeSet a = Node (TreeSet a) a (TreeSet a) | Nil deriving Show

powersetTree :: (Ord a) => TreeSet a -> [TreeSet a]
powersetTree Nil = [Nil]
powersetTree tree = 
  [addTreeSet subtree v | subtree <- pxs] ++ pxs where
    (Node l v r) = tree
    pxs = powersetTree (removeTreeSet tree v)

addTreeSet :: (Ord a) => TreeSet a -> a -> TreeSet a
addTreeSet Nil x = Node Nil x Nil
addTreeSet (Node l v r) x = 
  if x < v then 
    Node (addTreeSet l x) v r
  else if x > v then
    Node l v (addTreeSet r x) 
  else error "Duplicate element"

removeTreeSet :: (Ord a) => TreeSet a -> a -> TreeSet a
removeTreeSet Nil a = error "Can't remove from empty set"
removeTreeSet (Node l v r) x = 
 if v == x then
   unionTreeSet l r
 else if x < v then
   Node (removeTreeSet l x) v r
 else
   Node l v (removeTreeSet r x)

unionTreeSet :: (Ord a) => TreeSet a -> TreeSet a -> TreeSet a
unionTreeSet Nil Nil = Nil
unionTreeSet Nil r = r
unionTreeSet l Nil = l
unionTreeSet l (Node rl rv rr) = Node (unionTreeSet l rl) rv rr

buildTreeSet [] = Nil
buildTreeSet (x:xs) = addTreeSet ts x where ts = buildTreeSet xs

showTreeSet Nil = []
showTreeSet (Node l v r) = (showTreeSet l) ++ [v] ++ (showTreeSet r)

powerset' xs = 
  foldr (:) [] lists where
    tree = buildTreeSet xs
    treeList = powersetTree tree
    lists = map showTreeSet treeList

Вы можете попробовать это, запустив powerset' [1, 2, 3], что дает [[1,2,3],[2,3],[1,3],[3],[1,2],[2],[1],[]]

Некоторые примечания:

Эффективность : моей главной целью было написать простые функции, чтобы показать основную идею c (возможно, за исключением powerset'). Например, производительность buildTreeSet может быть легко улучшена с помощью хвостовой рекурсии с аккумулятором , например, так: 

buildTreeSet' l = build l Nil where
  build [] tree = tree
  build (x:xs) partTree = build xs (addTreeSet partTree x)

Другая явная проблема заключается в том, что если При упорядочении списка, заданного в качестве входных данных для buildTreeSet, построение дерева будет вырожденным, эффективно выступая в качестве связанного списка, что лишает смысла использование деревьев. То же самое относится к removeTreeSet и unionTreeSet, поскольку последнее просто объединяет два дерева в цепочку.

Обработка ошибок : я использовал error (что похоже на исключение в java или c ++) для простоты кода. Однако вы должны рассмотреть возможность использования таких типов, как Maybe или Either, чтобы указать, что функции могут не работать. Большое преимущество функционального программирования в том, что на возможность сбоя может указывать сигнатура функции, заставляющая программиста обрабатывать ошибки во время компиляции (проверяя, было ли возвращение Just или Nothing) вместо выдачи ошибок в время выполнения.

Вот пример для removeTreeSet: 

removeTreeSetSafe :: (Ord a) => TreeSet a -> a -> Maybe (TreeSet a)
removeTreeSetSafe Nil a = Nothing
removeTreeSetSafe (Node l v r) x = 
  if v == x then
    Just (unionTreeSet l r)
  else if x < v then
    let mTree = (removeTreeSetSafe l x) in
    case mTree of
      (Just tree) -> Just (Node tree v r)
      Nothing -> Nothing
  else
    let mTree = (removeTreeSetSafe r x) in
    case mTree of
      (Just tree) -> Just (Node l v tree)
      Nothing -> Nothing

Вот пример различия: 

> tree = buildTreeSet [1..4]
> tree
Node (Node (Node (Node Nil 1 Nil) 2 Nil) 3 Nil) 4 Nil
> removeTreeSet tree 2
Node (Node (Node Nil 1 Nil) 3 Nil) 4 Nil
> removeTreeSet Nil 2
*** Exception: Can't remove from empty set
CallStack (from HasCallStack):
  error, called at main.hs:24:23 in main:Main
> removeTreeSetSafe tree 2
Just (Node (Node (Node Nil 1 Nil) 3 Nil) 4 Nil)
> removeTreeSetSafe Nil 2
Nothing

В первом случае с removeTreeSet если элемент не найден или набор пуст, программа просто завершится с ошибкой (при условии, что он был скомпилирован).

Во втором случае, используя removeTreeSetSafe, мы вынуждены обрабатывать возможность сбоя, иначе код не скомпилируется (как вы не можете заменить removeTreeSet на removeTreeSetSafe)

...