Derive Ord with Quantified Constraints (forall a. Ord a => Ord (f a))

Question

With quantified constraints I can derive Eq (A f) just fine? However, when I try to derive Ord (A f) it fails. I do not understand how to use quantified constraints when the constraint class has a superclass. How do I derive Ord (A f) and other classes that have superclasses?

> newtype A f = A (f Int)
> deriving instance (forall a. Eq a => Eq (f a)) => Eq (A f)
> deriving instance (forall a. Ord a => Ord (f a)) => Ord (A f)
<interactive>:3:1: error:
    • Could not deduce (Ord a)
        arising from the superclasses of an instance declaration
      from the context: forall a. Ord a => Ord (f a)
        bound by the instance declaration at <interactive>:3:1-61
      or from: Eq a bound by a quantified context at <interactive>:1:1
      Possible fix: add (Ord a) to the context of a quantified context
    • In the instance declaration for 'Ord (A f)'

PS. I have also examined ghc proposals 0109-quantified-constraints. Using ghc 8.6.5

Kampala

Answer 1

The problem is that Eq is a superclass of Ord, and the constraint (forall a. Ord a => Ord (f a)) does not entail the superclass constraint Eq (A f) that's required to declare an Ord (A f) instance.

• We have (forall a. Ord a => Ord (f a))

• We need Eq (A f), i.e., (forall a. Eq a => Eq (f a)), which is not implied by what we have.

Solution: add (forall a. Eq a => Eq (f a)) to the Ord instance.

(I don't actually understand how the error message given by GHC relates to the problem.)

{-# LANGUAGE QuantifiedConstraints, StandaloneDeriving, UndecidableInstances, FlexibleContexts #-}

newtype A f = A (f Int)
deriving instance (forall a. Eq a => Eq (f a)) => Eq (A f)
deriving instance (forall a. Eq a => Eq (f a), forall a. Ord a => Ord (f a)) => Ord (A f)

Or a little more tidily:

{-# LANGUAGE ConstraintKinds, RankNTypes, KindSignatures, QuantifiedConstraints, StandaloneDeriving, UndecidableInstances, FlexibleContexts #-}

import Data.Kind (Constraint)

type Eq1 f = (forall a. Eq a => Eq (f a) :: Constraint)
type Ord1 f = (forall a. Ord a => Ord (f a) :: Constraint)  -- I also wanted to put Eq1 in here but was getting some impredicativity errors...

-----

newtype A f = A (f Int)
deriving instance Eq1 f => Eq (A f)
deriving instance (Eq1 f, Ord1 f) => Ord (A f)

Jenine

I was so close with deriving instance (forall a. (Eq a, Ord a) => (Eq (f a), Ord (f a))) => Ord (A f). Do you know why there is a difference? – Kampala

That doesn't imply forall a. Eq a => Eq (f a) either. (viewed in terms of logic (A /\ B) => (C /\ D) does not imply A => C) – Jenine

In fact what you wrote is equivalent to forall a. Ord a => Ord (f a). – Jenine