Power set using BST in haskell

Question

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!

Answer 1

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 this to work properly:

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

(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. mapTree is trivial (and already covered in your previous question); simultaneously accessing a node and its successor in the fringe is also doable.

---

As a curiosity, I include also a version which generates the longest sublists first, for comparison:

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

Answer 2

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.