Haskell - powerset of a Set

Question

I'm a beginner to Haskell.

I've implemented a set as a binary tree

Set a = Node a | Tree a (Set a) (Set a)

I've been stuck on creating a powers function. Any ideas on how I could implement a powerset function, ideally not completely the same as Data.Set 😅?

Answer 1

Let's look at a simpler version of powerset that uses lists:

powerset [] = [[]]
powerset (x:xs) = [x:ps | ps <- pxs] ++ pxs where
   pxs = powerset xs

Running powerset [1, 2, 3] yields [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

From this you can see basic functions and data definitions needed for implementing the operations with BSTs:

1. powerset [] = [[]] an empty set, which is missing in your case as pointed out in the comments
2. x:ps a way to add an element to a set
3. And, a more subtle one: removing an element from the set, because (x:xs) splits the set int x and xs which is used in pxs = powerset xs

A simple implementation would look like this:

data TreeSet a = Node (TreeSet a) a (TreeSet a) | Nil deriving Show

powersetTree :: (Ord a) => TreeSet a -> [TreeSet a]
powersetTree Nil = [Nil]
powersetTree tree = 
  [addTreeSet subtree v | subtree <- pxs] ++ pxs where
    (Node l v r) = tree
    pxs = powersetTree (removeTreeSet tree v)

addTreeSet :: (Ord a) => TreeSet a -> a -> TreeSet a
addTreeSet Nil x = Node Nil x Nil
addTreeSet (Node l v r) x = 
  if x < v then 
    Node (addTreeSet l x) v r
  else if x > v then
    Node l v (addTreeSet r x) 
  else error "Duplicate element"

removeTreeSet :: (Ord a) => TreeSet a -> a -> TreeSet a
removeTreeSet Nil a = error "Can't remove from empty set"
removeTreeSet (Node l v r) x = 
 if v == x then
   unionTreeSet l r
 else if x < v then
   Node (removeTreeSet l x) v r
 else
   Node l v (removeTreeSet r x)

unionTreeSet :: (Ord a) => TreeSet a -> TreeSet a -> TreeSet a
unionTreeSet Nil Nil = Nil
unionTreeSet Nil r = r
unionTreeSet l Nil = l
unionTreeSet l (Node rl rv rr) = Node (unionTreeSet l rl) rv rr

buildTreeSet [] = Nil
buildTreeSet (x:xs) = addTreeSet ts x where ts = buildTreeSet xs

showTreeSet Nil = []
showTreeSet (Node l v r) = (showTreeSet l) ++ [v] ++ (showTreeSet r)

powerset' xs = 
  foldr (:) [] lists where
    tree = buildTreeSet xs
    treeList = powersetTree tree
    lists = map showTreeSet treeList

You can try it by running powerset' [1, 2, 3] which yields [[1,2,3],[2,3],[1,3],[3],[1,2],[2],[1],[]]

Some notes:

Efficiency: my main goal above was to write the functions in simplest way to show the basic idea (maybe except powerset'). For example the performance of buildTreeSetcould be easily improved by using tail recursion with an accumulator like so:

buildTreeSet' l = build l Nil where
  build [] tree = tree
  build (x:xs) partTree = build xs (addTreeSet partTree x)

Another glaring problem is that if the list given as input to buildTreeSet is ordered, the tree build will be degenerate, effectively acting as a linked list, which defeats the point of using trees. The same applies for removeTreeSet and unionTreeSet because the latter just chains the two trees.

Error handling: I used error (which is like throwing an exception in java or c++) to keep the code simple. However you should consider using types like Maybe or Either to indicate that functions might fail. A big advantage of functional programming that the possibility of failure can be indicated by the signature of the function, forcing the programmer to handle errors at compile time (by checking if the return was Just or Nothing) instead of throwing errors at runtime.

Here's an example for removeTreeSet:

removeTreeSetSafe :: (Ord a) => TreeSet a -> a -> Maybe (TreeSet a)
removeTreeSetSafe Nil a = Nothing
removeTreeSetSafe (Node l v r) x = 
  if v == x then
    Just (unionTreeSet l r)
  else if x < v then
    let mTree = (removeTreeSetSafe l x) in
    case mTree of
      (Just tree) -> Just (Node tree v r)
      Nothing -> Nothing
  else
    let mTree = (removeTreeSetSafe r x) in
    case mTree of
      (Just tree) -> Just (Node l v tree)
      Nothing -> Nothing

Here is an example of the difference:

> tree = buildTreeSet [1..4]
> tree
Node (Node (Node (Node Nil 1 Nil) 2 Nil) 3 Nil) 4 Nil
> removeTreeSet tree 2
Node (Node (Node Nil 1 Nil) 3 Nil) 4 Nil
> removeTreeSet Nil 2
*** Exception: Can't remove from empty set
CallStack (from HasCallStack):
  error, called at main.hs:24:23 in main:Main
> removeTreeSetSafe tree 2
Just (Node (Node (Node Nil 1 Nil) 3 Nil) 4 Nil)
> removeTreeSetSafe Nil 2
Nothing

In the first case with removeTreeSet if an element is not found or the set is empty the program will simply exit with an error (assuming it was compiled).

In the second case using removeTreeSetSafe we are forced to handle the possibility of failure, else the code won't compile (as in you can't replace removeTreeSet with removeTreeSetSafe)