Power set using BST in haskell-CodePudding

I have implemented a Set datatype in Haskell using Binary search tree. I have not used any of the in-built functions nor imported any module.

My set datatype is as follows:

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

I have written a toList function , and a fromList function using insert function . I have also written a setmap, and a setfoldr function on sets using bst.

I am stuck on just one problem now:

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

I have no idea on how to implement a powerSet using this type signature. I don't have any clues on what kind of auxiliary functions I need to write for this. I have some clue on how to do this with Lists, but not using a binary search tree. If you could please share some hints on how to do this. Thanks in advance!

CodePudding user response：

Powersets are defined recursively.

The powerset of an empty set is the set containing an empty set.

P({}) = {{}}

The powerset P of a non-empty set S is found by first choosing an arbitrary element x and removing it from S to get S'. You recursively compete the powerset of S' to get P'. You then construct P as

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

So, as long as you have union :: Set a -> Set a -> Set a and remove :: Set a -> a -> Set a defined, it should be straightforward to translate the above definition into powerset :: Set a -> Set (Set a).

(I omitted the assumed Ord a constraint from all type signatures above.)

For example,

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

etc.

CodePudding user response：

You've mentioned you've implemented toList. You can use it to go the lists route here.

Just as in your previous question, this calls for implementing and using fromAscendingList, to construct a tree from a list in a purely structural manner, without any comparisons, under the assumption that the list is already ordered in an increasing order.

This structural construction doesn't involve any knowledge of the elements; same should be true for the powerset function:

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

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

Of course we need to implement powerList in an order-preserving fashion, for that to work properly:

powerList :: [a] -> [[a]]
powerList  =  concat . powers
  where
  powers :: [a] -> [[[a]]]
  powers (x:xs) =  let p = powers xs in [[]] : zipWith (  )
                        (map (map (x:)) p) (drop 1 p    [[]])
  powers []     =  [[[]]]

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

(a simpler alternative generates the sublists in a different order:

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

and if we'd followed the set-notation pseudocode in the other answer directly, the resulting code would produce the sublists even more out of order -- [3] would come out before [2], and that before [1]).

You still need to implement fromsAcendingList. The simplest way is to just create the highly-unbalanced, list-like tree. You can start with that. Then perhaps devise a way to create the nearly-balanced tree, which is preferable.

As an alternative, treat all of the above as an executable specification and re-implement it to work directly on your Set type values. map is trivial (and already covered in your previous question); clearly, zipWith for two equal-sized sets is well-defined.