我已經使用二叉搜索樹在 Haskell 中實作了 Set 資料型別。我沒有使用任何內置函式，也沒有匯入任何模塊。
我設定的資料型別如下：
data Set a = Empty | Node a (Set a) (Set a) deriving(Show)
我已經撰寫了一個 toList 函式和一個使用 insert 函式的 fromList 函式。我還使用 bst 在集合上撰寫了一個 setmap 和一個 setfoldr 函式。
我現在只解決一個問題：
-- powerset of a set
-- powerset {1,2} => { {}, {1}, {2}, {1,2} }
powerSet :: Set a -> Set (Set a)
我不知道如何使用這種型別簽名來實作 powerSet。對于我需要為此撰寫什么樣的輔助函式，我沒有任何線索。我對如何使用串列執行此操作有一些線索，但不使用二叉搜索樹。如果可以，請分享一些有關如何執行此操作的提示。提前致謝！
uj5u.com熱心網友回復：
你提到你已經實作了toList. 您可以使用它來執行此處的串列路線。
就像在您之前的問題中一樣，這需要實作和使用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) = let { p = powers xs } in
take 1 p [ map (x:) a c
| (a:b) <- tails p
, let c = if null b then [] else head b ]
{-
> powerList [1,2,3]
[[], [1],[2],[3], [1,2],[1,3],[2,3], [1,2,3]]
> mapM_ (print . powers) [[], [3], [2,3], [1,2,3]]
[ [[]] ]
[ [[]], [ [3]] ]
[ [[]], [ [2],[3]], [ [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是微不足道的（并且已經在您之前的問題中介紹過）；同時訪問邊緣節點及其后繼節點也是可行的。
uj5u.com熱心網友回復：
冪集是遞回定義的。
空集的冪集是包含空集的集合。
P({}) = {{}}
P非空集的冪集S是通過首先選擇一個任意元素x并將其從Sget 中洗掉來找到的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}}
等等。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/406842.html
標籤：
上一篇：如何在我的玩具語言中正確評估此值