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