Typeclass constraints with higher kinded types

4
votes

I'm trying to write an Eq instance for an EitherT newtype given by:

newtype EitherT e m a = EitherT { runEitherT :: m (Either e a) }

I assumed the following Eq instance would work:

instance (Eq e, Eq a, Eq m) => Eq (EitherT e m a) where
  a == b = (runEitherT a) == (runEitherT b)

However, I'm seeing an error:

Expected kind '* -> *', but 'm' has kind '*'

What I'm reading from that error is that my typeclass constraint ( ... Eq m) => ... is confusing the compiler into thinking that I believe m to be of kind *, when my newtype declaration for EitherT expects it to be of kind * -> *.

I'm wondering what I need to do, to declare that I want an Eq instance for some higher kinded type m to implement Eq for my EitherT newtype.

Edit: As pointed out by @AlexisKing, I can get this to work with:

{-# LANGUAGE UndecideableInstances #-}
instance (Eq (m (Either e a))) => Eq (EitherT e m a) where
  a == b = (runEitherT a) == (runEitherT b)

However, it seems strange to me to that a language extension is required to write this Eq instance. Is there no other way to express such a typeclass constraint in vanilla Haskell? If not, why?

2
haskell
You probably want Eq (m b), not Eq m. For what it’s worth, though, I think you could just have GHC derive this class for you, and it would figure out the necessary constraints. – Alexis King
@AlexisKing That gives a different error Variable 'b' occurs more often in the constraint 'Eq (m b)' than in the instance head. Also, ghc will not derive this typeclass for me, I'm not entirely sure why though. – Wilduck
You can turn on StandaloneDeriving and UndecidableInstances and write deriving instance Eq (m (Either e a)) => Eq (EitherT e m a). Alternatively, you can write the instance you currently have, but replace all your constraints with Eq (m (Either e a)). – Alexis King
Thanks for the help @AlexisKing. I'd like to try to write this Eq instance myself, if only to understand what's going on. However, using Eq (m (Either e a)) in the typeclass constraint produces a warning and asks me to turn on UndecidableInstances. Is it really not possible to write this instance without UndecidableInstances? If so, why? I'm going to edit my question to include this. – Wilduck
UndecidableInstances is safe. It allows type class resolution to be recursive in non-total ways. The worst thing that happens is the compiler gets stuck in a recursive loop. If the compiler terminates the resulting code is still safe. It's an extension because a compiler is expected to terminate. – Cirdec

2 Answers

7
votes

You're looking for Eq1 which is in Data.Functor.Classes since base 4.9.0.0. Before that it was in one of the -extras packages or transformers? (it's in transformers now since 0.4.0.0)

Eq1 f says that you can compare fs as long as you have a way to compare their contents

class Eq1 f where
    liftEq :: (a -> b -> Bool) -> f a -> f b -> Bool

In your case you'd use it like

instance (Eq e, Eq1 m) => Eq1 (EitherT e m) where
   liftEq f a b = liftEq (liftEq f) (runEitherT a) (runEitherT b)

The liftEq f is to use the existing Eq1 instance for Either.

And can define an Eq instance as

instance (Eq e, Eq a, Eq1 m) => Eq (EitherT e m a) where
   (==) = liftEq (==)

The old Eq1 was

class Eq1 f where
    eq1 :: (Eq a) => f a -> f a -> Bool

In your case you'd use it like

instance (Eq e, Eq1 m) => Eq1 (EitherT e m) where
   eq1 a b = eq1 (runEitherT a) (runEitherT b)

instance (Eq e, Eq a, Eq1 m) => Eq1 (EitherT e m) where
   a == b = eq1 (runEitherT a) (runEitherT b)
2
votes

It might be worth noting that this instance already exists in current versions of the either package (though not the old EitherT package, which is considered obsolete):

instance Eq (m (Either e a)) => Eq (EitherT e m a) where
  (==) = (==) on runEitherT

Of course, as @Alexis King has noted, it requires UndecidableInstances, but the either package is authored by Edward Kmett, a notorious dilettante and amateur who can't write proper Haskell98 like us real programmers. ;)