Haskell instance of typeclass definition with type constructor

Question

data CouldBe a = Is a | Lost deriving (Show, Ord)

instance Eq (CouldBe m) where
  Is x == Is y = x == y 
  Lost == Lost = True 
  _ == _ = False

Gives an error: No instance for (Eq m) arising from a use of ‘==’ So:

instance (Eq m) => Eq (CouldBe m) where
  Is x == Is y = x == y 
  Lost == Lost = True 
  _ == _ = False

Works fine (at least I start understanding the errors), but why do I need that constraint? I am trying to learn, so the 'why' is very important to me.

chepner chepner · Accepted Answer · 2019-03-07T16:53:43

Your original definition said that CouldBe m was an instance of Eq for any type m, even one that doesn't have an Eq instance. But if that's true, you have to find some way of defining Is x == Is y without using x == y (since you haven't required m to have an Eq instance, x == y isn't necessarily defined.)

As a specific example, it prevents you from writing something like

Is (+3) == Is (* 5)  -- (+3) == (*5) is undefined

Adding the constraint ensures you can compare two CouldBe values only if the wrapped type can also be compared.

A "valid", but trivial, instance without adding the constraint:

instance Eq (CouldBe m) where
  Is x == Is y = True
  Lost == Lost = True
  _ == _ = False

Two CouldBe m values are equal as long as they share the same data constructor, regardless of the wrapped value. No attempt is made to use x or y at all, so their types can be unconstrained.

"Valid" is in quotes because this definition could be in violation of the substitutivity law, defined at http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Eq.html. Suppose you had a function that could pull apart a CouldBe value:

couldbe :: b -> (a -> b) -> CouldBe a -> b
couldBe x _ Lost = x
couldBe _ f (Is x) = f x

The violation occurs because Is 3 == Is 5 would be true, but let f = couldbe 0 id. Then f (Is 3) == f (Is 5) evaluates to 3 == 5 which is false.

Whether it's actually a violation or not depends on the existence of a function like couldbe that can see "inside" a CouldBe value.

Haskell instance of typeclass definition with type constructor

1 Answers