在哈斯克尔中使用BST进行电源设置

Question

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

我设置的数据类型如下：

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

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

我现在只遇到一个问题：

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

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

Answer 1

Powerset 以递归方式定义。

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

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.您可以使用它在此处进行列表路由。

就像你之前的问题一样，这需要实现和使用fromAscendingList，以纯粹的结构方式从列表中构建一棵树，没有任何比较，假设列表已经按递增顺序排序。

这种结构结构不涉及任何元素知识;对于幂集函数也应该如此：

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是微不足道的(并且已经在您之前的问题中涉及);同时访问边缘节点及其后继节点也是可行的。

---

出于好奇，我还包含一个首先生成最长子列表的版本，以进行比较：

-- 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]],  [[]]]