Instance Eq is not working in Haskell

Question

So I was given the following data type and I had to write a code that checks if an element is in the list (I think I did this one right). After this I had to declare instance Eq where it would be True if both of my amount lists would be equal. I was supposed to use the element code I wrote earlier. Could someone tell me what I am doing wrong?

   data Amount a = Amount [a] 

element [] _ = False
element (x:xs) y = ( x==y) || element xs y

instance Eq (Amount a) where 
      Amount xs == Amount ys = element xs ys && element ys xs

This is the error message I am receiving

 • Couldn't match expected type ‘a’ with actual type ‘[a]’
      ‘a’ is a rigid type variable bound by
        the instance declaration at Probeklausur1.hs:43:10-22
    • In the second argument of ‘element’, namely ‘ys’
      In the first argument of ‘(&&)’, namely ‘element xs ys’
      In the expression: element xs ys && elementS ys xs
    • Relevant bindings include
        ys :: [a] (bound at Probeklausur1.hs:44:27)
        xs :: [a] (bound at Probeklausur1.hs:44:14)
        (==) :: Amount a -> Amount a -> Bool
          (bound at Probeklausur1.hs:44:17)
   |
44 |       Amount xs == Amount ys = element xs ys && elementS ys xs     |                                           ^^

Probeklausur1.hs:44:49: error:
    • Variable not in scope: elementS :: [a] -> [a] -> Bool
    • Perhaps you meant ‘element’ (line 40)
   |
44 |       Amount xs == Amount ys = element xs ys && elementS ys xs     |                                                 ^^^^^^^^

Answer 1

Let us first analyze the type of element:

element [] _ = False
element (x:xs) y = ( x==y) || element xs y

We see that the first item is a list [a] (based on the [] and (:) data constructors). Furthermore we know that the second item has as type the type of the elements of the list, so a, and since we call x == y, there must be an Eq a constraint. So we derive:

element :: Eq a => [a] -> a -> Bool

A very similar builtin function already exists for this: elem :: Eq a => a -> [a] -> Bool, so it is probably better to use this one instead.

But let us now look at the instance declaration:

instance Eq (Amount a) where 
    Amount xs == Amount ys = element xs ys && element ys xs

There are two problems here:

1. we need a to have an Eq type constraint as well, since we need to check if the elements of the list are the same; and
2. we call element with xs and ys, but both xs and ys have type [a], so this will not work.

We thus first need a mechanism to check that all elements of one list occur in the other list. We can check this with the all :: (a -> Bool) -> [a] -> Bool function:

allElem :: Eq a => [a] -> [a] -> Bool
allElem xs = all (flip elem xs)

So now we can write it like:

instance Eq a => Eq (Amount a) where 
    Amount xs == Amount ys = allElem xs ys && allElem ys xs

Note that the above might still not be exactly what you want for two reasons:

1. the order of the two lists is not checked, I assume that this is intentional;
2. if an element occurs multiple times in the first list, then it does not have to occur that many times in the second list, as long as it occurs at least once we are fine. The length of the two lists can thus be different, and still the two Amounts are considered equal.