Cartesian product of two sets using BST in Haskell

Question

I am using a Binary search tree to implement a set datatype in Haskell. I came across a problem, and tried it for really long, and gave up finally. Can you please help me out with the solution?

My Set datatype is implemented as follows:

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

I wanted to make the following functions:

 -- cartesian product of two sets
 cartesian :: Set a -> Set b -> Set (a, b)
 cartesian =   

 -- join two Sets together
 -- be careful not to introduce duplicates.
 union :: (Ord a) => Set a -> Set a -> Set a
 union = 

I am aware of implementing these functions on a list, but not on a set, especially because I have implemented it in the form of a BST. That's the reason I am really confused on what my steps must be. I cannot change the set to a list, and then solve the function, as the ORD constraint is not defined in my type signature of the cartesian function.

My confusion in the union function was that, how do I avoid the duplicates without using the EQ constraint?

I cannot use the Data.Set module or any other prelude functions. I cannot change the type signature as well.

My setmap function:

 setmap :: (Ord b) => (a -> b) -> Set a -> Set b
 setmap f Empty = Empty
 setmap f (Node val l r) = Node (f val) (setmap f l) (setmap f r) 

My setfoldr function:

 setfoldr :: (a -> b -> b) -> Set a -> b -> b
 setfoldr f Empty acc = acc 
 setfoldr f (Node val l r) acc = setfoldr f (f val (setfoldr f r 
 acc)) l  

My setfoldr function is giving an error; if you could help me out with this as well . thanks

Thanks in advance,

Answer 1

To implement the Cartesian product, you don't need to compare the elements. The trees have already been built in order. For any value a anywhere in the first tree tree1, you can build a tree treeMap (a ,) tree2 which will maintain the second tree's order, since all the first entries in the tuples are the same. Then you can just replace that a with this new tree, and the new combined tree -- which will be the Cartesian product of the two -- will also be in order, the lexicographical order.

This indeed assumes there are no duplicates in the first tree.

So, implementing treeMap :: (b -> c) -> Set b -> Set c is easy (treating is as a tree, not even a BST nor as a Set, as @amalloy mentions in the comments; just a structural mapping function), and you'll end up with the Set (Set (a,b)) tree. Now, smashing this back into Set (a,b) is also easy, since the (a,b) values are already ordered, by construction. So after enumeration you'll get an ordered nested list, which you can then concatenate, and fold the resulting list back into the valid search tree without ever needing to compare the tuples, just doing it positionally.

Assuming you've implemented treeFoldr and treeMap with expected semantics, this could be coded as

setCrossProd :: Set a -> Set b -> Set (a,b)
setCrossProd s1 s2 = fromAscendingList abs
  where
  abs = concatMap toList nested  -- abs :: [(a,b)]
  nested = toList crossed   -- nested :: [Set (a,b)]
  -- toList :: Set a -> [a]
  toList t = treeFoldr (:) [] t
  crossed = mapTree       -- crossed :: Set (Set (a,b))
              (\a -> mapTree (\b -> (a,b)) s2)
              s1
  -- fromAscendingList :: [a] -> Set a
  fromAscendingList xs = ...... 

(or something like that; not tested). The point of having fromAscendingList :: [a] -> Set a is that the list is already known / assumed to be sorted, so we won't perform any comparisons: we know / assume that any element that comes later is bigger than the one before it, positionally, in the list. It has no constraint in its type, as it won't perform any inserts; it will construct the trees structurally right away.

About your setfoldr function, you just need to move l to be the 2nd parameter, not 3rd, in the second equation:

setfoldr :: (a -> b -> b) -> Set a -> b -> b
setfoldr f Empty acc = acc 
setfoldr f (Node val l r) acc =      -- f   ::     a -> b -> b
  setfoldr f l                       -- l   :: Set a
             (f val                  -- val ::     a
                (setfoldr f r        -- r   :: Set a
                            acc))    -- acc ::          b

Just like r is in the 2nd position, so must be l. This is also seen in setfoldr's type. Follow the types.

---

As to the issue of implementing the union, you already have the Eq constraint when you have Ord, because Eq is a superclass of Ord:

> :i Ord
class Eq a => Ord a where
  compare :: a -> a -> Ordering
  .......

any Ord type must also be an Eq type.