在 haskell 中使用 BST 的幂集

Question

我已经使用二叉搜索树在 Haskell 中实现了一个 Set 数据类型。我没有使用任何内置功能，也没有导入任何模块。

我设置的数据类型如下：

data Set a = Empty | Node a (Set a) (Set a) deriving(Show)

我已经编写了一个 toList 函数，以及一个使用插入函数的 fromList 函数。我还使用 bst 在集合上编写了一个 setmap 和一个 setfoldr 函数。

我现在只遇到一个问题：

-- powerset of a set
-- powerset {1,2} => { {}, {1}, {2}, {1,2} }
powerSet :: Set a -> Set (Set a)

我不知道如何使用这种类型签名实现 powerSet。我不知道我需要为此编写什么样的辅助功能。我对如何使用列表执行此操作有一些线索，但不使用二叉搜索树。如果可以，请分享一些有关如何执行此操作的提示。提前致谢！

Answer 1

幂集是递归定义的。

空集的幂集是包含空集的集合。

P({}) = {{}}

非空集S的幂集P是通过首先选择任意元素x并将其从S中移除得到S'.您递归地竞争 S' 的幂集以获得 P'。然后将 P 构造为

P = P' ∪ { s ∪ {x} | s ∈ P' }

因此，只要定义了union :: Set a -> Set a -> Set a和remove :: Set a -> a -> Set a，将上面的定义翻译成powerset :: Set a -> Set (Set a).

应该很简单

（我从上面的所有类型签名中省略了假定的 Ord a 约束。）

例如，

P({}) == {{}}
P({1}) == {{}} ∪ {{1}}
       == {{}, {1}}
P({1,2}) == {{}, {1}} ∪ {{2}, {1,2}}
         == {{}, {1}, {2}, {1,2}}

等等

Answer 2

您提到您已经实现了 toList。您可以在此处使用它进入列表路线。

就像在您的 previous question 中一样，这需要实现和使用 fromAscendingList，以纯粹结构化的方式从列表构建树，没有任何比较，假设列表已经按升序排列了。

这种结构构造不涉及任何元素知识； powerset 函数也应如此：

powerSet :: Set a -> Set (Set a)
powerSet = toList >>> powerList >>> map fromAscendingList
                  >>> fromAscendingList

-- (foo >>> bar >>> baz) x = baz (bar (foo x))

当然，我们需要以保序方式实现 powerList，才能正常工作：

powerList :: [a] -> [[a]]
powerList  =  concat . powers
  where
    powers :: [a] -> [ [[a]]]
    powers []     =  [ [[]] ]
    powers (x:xs) =  [ [[]] ] ++
         [ map (x:) a ++ b 
           | (a:b:_) <- tails (powers xs ++ [[]]) ]

-- > powerList [1,2,3]
-- [[],  [1],[2],[3],  [1,2],[1,3],[2,3],  [1,2,3]]

（一个更简单的替代方案以不同的顺序生成子列表：

powerList' :: [a] -> [[a]]
powerList' (x:xs) = [ s | s <- powerList' xs, s <- [s, x:s]]
powerList' []     = [[]]

-- > powerList' [1,2,3]
-- [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

如果我们直接遵循另一个答案中的集合符号伪代码，生成的代码将产生更乱序的子列表——[3] 会在 [2] 之前出现, 以及 [1]).

之前

您还需要实施 fromsAcendingList。最简单的方法是创建高度不平衡的列表树。你可以从那开始。然后也许设计一种方法来创建接近平衡的树，这是更可取的。

作为替代方案，将以上所有内容视为可执行规范并重新实现它以直接处理您的 Set 类型值。 mapTree 是微不足道的（并且已经包含在您的 previous question 中）；同时访问边缘节点及其后继节点也是可行的。

出于好奇，我还提供了一个首先生成最长子列表的版本，以供比较：

-- shortest first:
powers :: [a] -> [ [[a]]]
powers []     =  [ [[]] ]
powers (x:xs) =  [ [[]] ] ++
     [ map (x:) a ++ b |  (a:b:_) <- tails (powers xs ++ [[]]) ]

-- longest first:
rpowers :: [a] -> [ [[a]]]
rpowers []     =  [ [[]] ]
rpowers (x:xs) = 
     [ map (x:) b ++ a |  (a:b:_) <- tails ([[]] ++ rpowers xs) ] 
      ++          [ [[]] ] 

> powers [1,2,3]
[[[]],  [[1],[2],[3]],  [[1,2],[1,3],[2,3]],  [[1,2,3]]]

> rpowers [1,2,3]
[[[1,2,3]],  [[1,2],[1,3],[2,3]],  [[1],[2],[3]],  [[]]]

在 haskell 中使用 BST 的幂集

Power set using BST in haskell

haskell

set

powerset