Haskell - Compile Error

1
votes
data Set a = Set [a]
member xs x = elem x xs
subset xs ys = and (map (member ys) xs)

instance (Eq a) => Eq (Set a) where  
  (Set xs) == (Set ys) = (subset xs ys) && (subset ys xs)

class Ord a => Comparable a where
  cmp :: a -> a -> String
  cmp x y
    | x == y    = "eq"
    | otherwise = "neq"

instance Comparable a => Comparable (Set a) where
  cmp (Set xs) (Set ys)
    | (Set xs) == (Set ys) = "same"
    | otherwise            = "different"

I'm getting the following error:

Could not deduce (Ord (Set a)) arising from the superclasses of an instance declaration from the context (Comparable a) bound by the instance declaration for ‘Comparable (Set a)’

I'd like to know what the error is? Thanks.

3
haskellcompiler-errors

3 Answers

1
votes

This declaration

class Ord a => Comparable a where

states that every member of the class Comparable must be a member of class Ord. If I were to attempt doing

data MyType = ...
instance Comparable MyType where
  cmp x y = "hello"

the compiler would complain that an instance Ord MyType is missing. IT does not matter that I am not using anything from that Ord instance: it is required by the definition of Comparable.

To fix that, add an instance

instance Ord a => Ord (Set a) where
   compare setA setB = ....

After that, you can use your Comparable instance, provided you add Ord a to the constraints.

instance (Ord a , Comparable a) => Comparable (Set a) where
  cmp (Set xs) (Set ys)
    | (Set xs) == (Set ys) = "same"
    | otherwise            = "different"
1
votes

Comparable is a subclass of Ord so you need to add an instance for Ord (Set a) e.g.:

instance Ord a => Ord (Set a) where
  compare (Set s1) (Set s2) =
    compare (sort s1) (sort s2)
0
votes

You gave a instance of Equality to your set data type but it doesn't have an Ord instance. When you try to make Set and instance of the Comparable class it requires that Set must be an instance of Ord.