CODEWITHSUNDEEP
haskell
Matthias Braun
Matthias Braun

Reputation: 34353

Why must element type of list be Eq when checking for empty list

The following reverse' function has type Eq t => [t] -> [t]:

reverse' list | list == [] = []
              | otherwise  = (reverse' listTail) ++ [listHead]
                where (listHead : listTail) = list

Why must the elements of the list be members of the typeclass Eq? I'm not comparing the elements for equality but the list they are contained in.

In my intuition, the list of t must be equatable, but t itself doesn't.

Upvotes: 1

Views: 293

Answers (2)

daniel gratzer
daniel gratzer

Reputation: 53881

This is because we can only compare lists in general for equality if we can compare their elements for equality. That is, in the general case there's no real way to explain [a, b, c] == [d, e, f] unless we can explain a == d.

This is reflected in the type of (==) on lists which after all works for both your case and the more generalized one:

 (==) :: (Eq a) => [a] -> [a] -> Bool

However you don't want to compare a list of equality with another list really, you just want to check whether a list is empty and so

 null :: [a] -> Bool

is a far better choice for you. And it doesn't have that equality constraint because it just uses pattern matching on the structure of the list, something that never requires a type class constraint.

  null :: [a] -> Bool
  null [] = True
  null (_ : _) = False

Even better in your case would be to just do the pattern matching yourself, after all, you're already right by a pattern!

reverse' [] = []
reverse' (listHead : listTail) = (reverse' listTail) ++ [listHead]

This is much closer to idiomatic Haskell because verifying that it doesn't crash can be done trivially by the compiler, we've exhaustively covered all cases in a way that it can check. In your version, to verify that the code would work we had to trace the two paths through the code and ensure an empty list would never end up in the branch where we had done that pattern match. This is only a small problem right now, but it will creep up in difficulty very quickly.

Upvotes: 8

Zeta
Zeta

Reputation: 105886

Because (==) :: Eq a => a -> a -> Bool only works for instances of Eq, and [] is only an instance of Eq if its elements are an instance of Eq:

instance (Eq a) => Eq [a] where
    ...

Instead, use null :: [a] -> Bool or pattern matching to check whether a list is empty:

reverse' [] = []
reverse' xs = ...

Upvotes: 5

Related Questions