I require comparison between two Htrees and to do so i implemented my own comparison function which i use together with sortBy, however i want to implement a derived instance of the Eq and Ord classes but the amount of cases needed to cover all possible combinations makes it impractical.
data Htree a b = Leaf a b
| Branch a (Htree a b) (Htree a b)
deriving (Show)
instance (Eq a) => Eq (Htree a b) where
(Leaf weight1 _ ) == (Leaf weight2 _) = weight1 == weight2
(Branch weight1 _ _) == (Leaf weight2 _) = weight1 == weight2
(Leaf weight1 _ ) == (Branch weight2 _ _) = weight1 == weight2
(Branch weight1 _ _) == (Branch weight2 _ _) = weight1 == weight2
As you can see, i just want to compare a single part of the Htree, Which will be an Integer in the actual code, and i need to write four cases for it. is there a way to generalize this so i can write it in just a single case? If i compare two Htree, compare their Integer parts?
what i currently use to compare two htree is:
comparison :: Htree Integer (Maybe Char) -> Htree Integer (Maybe Char) ->
Ordering
comparison w1 w2 = if(getWeight(w1) > getWeight(w2)) then GT
else if(getWeight(w1) < getWeight(w2)) then LT
else EQ
where getWeight is defined as:
getWeight :: Htree Integer (Maybe Char) -> Integer
getWeight(Leaf weight _) = weight
getWeight(Branch weight _ _) = weight
To do what you want, first write a more general version (that is, a polymorphic version) of getWeight, which only requires rewriting the type signature:
getWeight :: Htree a b -> a
getWeight(Leaf weight _) = weight
getWeight(Branch weight _ _) = weight
Then you can do the following (after importing the on function from Data.Function - I have also rewritten to make them point free as recommended by @FyodorSolkin)
instance (Eq a) => Eq (Htree a b) where
(==) = (==) `on` getWeight
instance (Ord a) => Ord (Htree a b) where
compare = compare `on` getWeight