Migrate away from Eq1/Ord1/Show1

[Bodigrim]

Continuing on haskell/core-libraries-committee#190 (comment), I propose to migrate from

instance Eq1 f => Eq (Fix f)
instance Ord1 f => Ord (Fix f)
instance Show1 f => Show (Fix f)

to

instance Eq (f (Fix f)) => Eq (Fix f)
instance Ord (f (Fix f)) => Ord (Fix f)
instance Show (f (Fix f)) => Show (Fix f)

or if you fancy QuantifiedContraints

instance (forall a. Eq a => Eq (f a)) => Eq (Fix f)
instance (forall a. Ord a => Ord (f a)) => Ord (Fix f)
instance (forall a. Show a => Show (f a)) => Show (Fix f)

The motivation is that I recently migrated a codebase from a homegrown newtype Fix with instance Ord (f (Fix f)) => Ord (Fix f) to data-fix and hit performance issues. They were a combination of several factors:

• I used Data.Functor.Classes.Generic to derive Ord1 instance generically. It appeared that from and to survived in Core, despite pretty aggressive optimization options. This is admittedly not a fault of data-fix, but a general issue with usability of Eq1 / Ord1 / Show1. I had to write all instances manually.

• class Ord1 contains only liftCompare, but no liftLT, liftLE, liftGT, liftGE, so it has no access to <, <=, >=, > of the base functor. This implies that < on Fix f also necessarily goes through compare and takes a performance hit.

• It does not seem that liftEq / liftCompare can be optimized away unless the base functor f is completely monomorphic and everything is forced to inline. E. g., (==) specialised to Fix (ListF Int) looks reasonable, but (==) for Fix (ListF a) goes through liftEq. The Core for

  instance Eq (f (Fix f)) => Eq (Fix f) where
    (==) = coerce ((==) @(f (Fix f)))

  looks more reasonable to me.

---

I understand that the proposed change is a breaking one. It is however not very pronounced: in recent base we have class (forall a. Eq f a) => Eq1 f, so the majority of users will not even notice. It's only if you require Eq (Fix f) as a constraint, but use liftEq inside, which will explode, because Eq1 f is no longer guaranteed. I think, however, that GHC would yell if encounters Eq (Fix f) constraint, suggesting to replace it with Eq1 f.

@phadej what do you think?

[phadej]

Please write a patch and check what happens with at least few direct dependencies (from https://packdeps.haskellers.com/reverse/data-fix, e.g. dhall, hnix, liquidhaskell-boot) with various GHCs, including the oldest supported (GHC-8.4 or 8.6 it seems)

[phadej]

Does #29 solve the optimisation problem? You'd still need Eq1/Ord1 instances, but that's should be an acceptable price (you already have them anyway).

[Bodigrim]

Yes, looks good.

[phadej]

Done in #29