Haskell - cartesian function for set implemented as binary tree

Question

I have implemented a set as a binary tree in Haskell as such:

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

and I'm trying to define a function to find the Cartesian product of two sets like so

cartesian :: Set a -> Set b -> Set (a, b)
cartesian as bs = fromList [(a,b) | a <- (toList as), b <- (toList bs)]

I can't seem to see what the error with this code is, any help/fixes would be appreciated.

The error message is:

error:
    • No instance for (Ord a) arising from a use of ‘fromList’
      Possible fix:
        add (Ord a) to the context of
          the type signature for:
            cartesian :: forall a b. Set a -> Set b -> Set (a, b)
    • In the expression:
        fromList [(a, b) | a <- (toList as), b <- (toList bs)]
      In an equation for ‘cartesian’:
          cartesian as bs
            = fromList [(a, b) | a <- (toList as), b <- (toList bs)]

Answer 1

Your fromList function assumes that it receives an unsorted list that may contain duplicates, so it needs an Ord constraint to figure out where to put the elements, and to clean up the duplicates. However, in this case, you're getting two lists that will always be sorted and not contain duplicates, and taking their Cartesian product, and the resulting list will also be sorted and not contain duplicates. Rather than using fromList to turn this new list into a set, you should create a new function for this purpose, just like fromDistinctAscList in the real Set. To build this, unroll foldr insert Node (I would show you how to do this, but you didn't post your insert function, so I can't), and replace all comparisons with the hardcoded result based on where they were. Then, just use it in place of fromList. This will also give a performance benefit, since it saves having to do all of the redundant comparisons.

Edit: your insert function doesn't care at all about maintaining any sort of balance of the binary tree, so calling it on a sorted list will produce a maximally unbalanced tree. If you don't care about that, then here's how you can implement fromDistinctAscList:

insertLeast :: a -> Set a -> Set a
insertLeast x Leaf = singleton x
insertLeast x (Tree a left right) = Tree a (insertLeast x left) right

fromDistinctAscList :: [a] -> Set a -> Set a
fromDistinctAscList = foldr insertLeast Leaf

Those have the exact same behavior as insert and fromList when there's no duplicates and elements are in ascending order. However, it has the unfortunate consequence of being a strict foldr, which is bad. We can optimize it a bit like this:

fromDistinctAscList :: [a] -> Set a -> Set a
fromDistinctAscList = foldr (`Tree` Leaf) Leaf

It will still be maximally unbalanced, though, but now in the other direction.

And you can also make your regular insert function lazier too:

insert :: Ord a => a -> Set a -> Set a
insert x xs = uncurry (Tree x) $ case xs of
  Node -> (Node, Node)
  Tree a left right -> case a `compare` x of
    LT -> (insert a left, right)
    EQ -> (left, right)
    GT -> (left, insert a right)

Answer 2

As the error says, your fromList fuction has an Ord a type constraint:

fromList :: Ord a => [a] -> Set a
fromList = foldr insert Node

So that means that in order to use the fromList function the a should be a member of the Ord typeclass. But that is not in the signature of your cartesian function.

Like the error says, you can add that type constraint to your cartesian function:

cartesian :: (Ord a, Ord b) => Set a -> Set b -> Set (a, b)
cartesian as bs = fromList [(a,b) | a <- toList as, b <- toList bs]

The Ord a, Ord b type constraints arise from the fact that a 2-tuple is an instance of Ord given the two elements are an element instance of Ord. Indeed, the instance is defined as:

instance (Ord a, Ord b) => Ord (a, b) where
    -- …