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!

Placative

So you know how to write toList, how to find a power set of a list, and how to write fromList, but not how to find a power set of a Set? – Sippet

"If you could please share the code with me for this function." <-- voting to close. – Glucoprotein

@MichaelLitchard- I just need some hints, have edited that line, thanks – Placative

@JosephSible-ReinstateMonica, Yes, I wrote all the other functions, but I am not sure on how to write this one, using this type signature – Placative

@JosephSible-ReinstateMonica NB that's fromList, not fromAscendingList. so they need insert, which needs Ord on Sets. perhaps that's the problem they are having. they really should implement fromAscendingList to use here (and in the previous question where I've left that function unimplemented and they haven't followed up on that). – Sievert

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

Sievert

Hey. Thanks for your answer. Is the fromAscendingList something like this: inser :: a-> Set a -> Set a inser a Empty = singleton a inser a (Node val l r) = Node val (inser a l) r frmAsclst :: [a] -> Set a frmAsclst = foldr inser Empty /// – Placative

yes, that works (you can just try it at the GHCi REPL and see for yourself). of course it's of the worse variety, the one with the highly unbalanced, what's known as "degenerate", shape. but it works; you can check that toList (frmAsclst xs) recreates the original list xs. next, try using manual recursion to create the more balanced tree. if you have the first half, the middle element, and the second half, then .... (try finishing this up). or you could have your inser making the tree rotations as needed. – Sievert

I am trying to execute the powerset function, but it keeps throwing an error , even though the logic is correct. The couldn't match expected type and actual type error. For example: Expected: Set a0 -> Set a -> Set (Set a) Actual: Set a0 -> [a0] , for the toList function. – Placative

I've tested with frmAsclst [1..3] & powerSet & toList & map toList and it works. (with x & f = f x) – Sievert

what is your toList code? edit your question to include it maybe. you said you implemented it already? where exactly is the problem? in any case, perhaps make a new post with all the code included in one place, i.e. post a new question. this answer already answers the question as asked. new question -- new post, is the SO way. :) you should close this (and the previous) question by accepting the most helpful answer (if any) and move on. – Sievert

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.

Fewer

you really don't need to (and by that I mean, shouldn't) be comparing the subsets to build the powerset. it's just a structural construction. also, pickOne :: Set a -> (a, Set a) seems a better choice. ;) (it is called only for the non-empty sets, by construction). – Sievert

pickOne is a good idea. I don't see where I'm comparing any subsets. (The last block is just supposed to be ASCII math, not Haskell pseudocode.) – Fewer

you did write you've "omitted the assumed Ord a constraint"... and union needs to compare the elements, and these elements are Sets. (or maybe not... ?) – Sievert

yes they are, in the P' ∪ ... part (not in the s ∪ {x} part). – Sievert

Are you proposing the type of powerset be changed to Set a -> [Set a]? Any function operating on a BST is going to need an Ord a constraint. – Fewer

I've added an answer that shows how to do it without the constraint. – Sievert