Comparing 2 Similar Types?

Question

I have 2 types, Tree and BinTree. The way I implement compare is like so:

instance (Eq a) => Ord (Tree a) where
  t <= u = traces t `subseteq` traces u

instance (Eq a) => Eq (Tree a) where
  t == u = traces t `subseteq` traces u && traces u `subseteq` traces t

instance (Eq a) => Ord (BinTree a) where
  t <= u = traces t `subseteq` traces u

instance (Eq a) => Eq (BinTree a) where
  t == u = traces t `subseteq` traces u && traces u `subseteq` traces t

As you can see, my traces function is happy to operate on both Tree and BinTree, thus there should be a way for me to do: myBinTree < myTree

Thus comparing a BinTree to a Tree

How does one go about implementing this so that BinTrees and Trees can be compared, since a BinTree is a subset of a Tree.

Answer 1

Not in such way that it becomes an instance of the Eq or Ord classes. These classes have the signature:

(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool

and so on...

You could write your own (==) function, but then that function becomes ambiguous, and as a result you will always need to specify about which (==) operator you are actually talking.

The answer to your comment "How does haskell compare floats to integers?" is that it doesn't. If you write:

> (1 :: Int) == (1.0 :: Float)

<interactive>:56:16:
    Couldn't match expected type `Int' with actual type `Float'
    In the second argument of `(==)', namely `(1.0 :: Float)'
    In the expression: (1 :: Int) == (1.0 :: Float)
    In an equation for `it': it = (1 :: Int) == (1.0 :: Float)

You see that the comparison can't be done. You can do this by converting:

> fromIntegral (1 :: Int) == (1.0 :: Float)
True

Where fromIntegral is a function that converts the Int into - in this case - a Float. You can do the same by implementing a bin2tree function.

You can of course define your own similar class:

class Similar a b where
    (=~) :: a -> b -> Bool
    (/=~) :: a -> b -> Bool
    (/=~) x y = not $ x =~ y

(and add {-# LANGUAGE MultiParamTypeClasses #-} in the file as modifier).

And then for instance:

instance (Similar a b) => Similar [a] [b] where
    (=~) [] [] = True
    (=~) _  [] = False
    (=~) [] _  = True
    (=~) (x:xs) (y:ys) = (x =~ y) && (xs =~ ys)

But the problem is that you will have to redefine a lot of methods yourself (that take use of Eq like nub) such that they work with your Similar class.