Proposal: Relax instances for Functor combinators; put superclasses on <class>1 to make less-breaking

[Ericson2314]

Implementation https://gitlab.haskell.org/ghc/ghc/-/merge_requests/4727

The first change makes the Eq, Ord, Show, and Read instances for Sum, Product, and Compose match those for :+:, :*:, and :.:. These have the proper flexible contexts that are exactly what the instance needs:

For example, instead of

instance (Eq1 f, Eq1 g, Eq a) => Eq (Compose f g a) where
  (==) = eq1

we do

deriving instance Eq (f (g a)) => Eq (Compose f g a)

But, that change alone is rather breaking, because until now Eq (f a) and Eq1 f (and respectively the other classes and their *1 equivalents too) are incomparable constraints. This has always been an annoyance of working with the *1 classes, and now it would rear it's head one last time as an pesky migration.

Instead, we give the *1 classes superclasses, like so:

(forall a. Eq a => Eq (f a)) => Eq1 f

along with some laws that canonicity is preserved, like:

liftEq (==) = (==)

and likewise for *2 classes

(forall a. Eq a => Eq1 (f a)) => Eq2 f

along with some laws that canonicity is preserved, like:

liftEq2 (==) = liftEq1

The *1 classes also have default methods using the *2 classes where possible.

What this means, as explained in the docs in my implementation, is that *1 classes really are generations of the regular classes, indicating that the methods can be split into a canonical lifting combined with a canonical inner, with the super class "witnessing" the laws[1] in a fashion.

Circling back to the pragmatics of migrating, note that the superclass means evidence for the old Sum, Product, and Compose instances is (more than) sufficient, so breakage is less likely --- as long no instances are "missing", existing polymorphic code will continue to work.

Breakage can occur when a datatype implements the *1 class but not the corresponding regular class, but this is almost certainly an oversight. For example, containers made that mistake for Tree and Ord, which I fixed in haskell/containers#761, but fixing the issue by adding Ord1 was extremely uncontroversial.

---

[1]: In fact, someday, when the laws are part of the language and not
only documentation, we might be able to drop the superclass field of the
dictionary by using the laws to recover the superclass in an
instance-agnostic manner, e.g. with a non-overloaded function with
type:

DictEq1 f -> DictEq a -> DictEq (f a)

But I don't wish to get into optomizations now, just demonstrate the
close relationship between the law and the superclass.

[Ericson2314]

When I rebased this, I found that Generically1 was missing Eq, Ord, Show, and Read instances, even though it had the *1 versions. Classic!

[Ericson2314]

haskellari/some#21 This is an example of an downstream library improvement that is blocked on this change.

GShow f = forall a. Show (f a) for all intents and purposes, but we cannot make a superclass to indicate (half of) that because the GShow instances for Sum and Product conflict with the overly-conservative Show1-based instances we have today, instead of the strictly more general instances proposed here.

[gwils]

The canonicity law looks good to me -- I'm actually surprised that Eq1 and co didn't already have something like this. The quantified constraint superclass also looks fine and sensible to me.
If we're going to use FlexibleContexts-style Eq (f a) constraints around the place after this change, what reason do Eq1 and co still have for existing? I thought their main purpose was to avoid such FlexibleContexts-style code.

Do we know how much of hackage this breaks? It looks like there was some effort to run this against head.hackage but nobody understood the outcome?

[Ericson2314]

If we're going to use FlexibleContexts-style Eq (f a) constraints around the place after this change, what reason do Eq1 and co still have for existing? I thought their main purpose was to avoid such FlexibleContexts-style code.

Besides back-compat (just getting rid of the classes altogether would be far more breaking), the classes are still meaningful if one wants to lift a non-canonical function on the inside. I am not sure how often that is done, but it's theoretically useful enough that I don't feel inspired to rid of this.

Do we know how much of hackage this breaks? It looks like there was some effort to run this against head.hackage but nobody understood the outcome?

I will try running it again. I think it was just broken then, but might work now.

[Bodigrim]

Eq1 class is still meaningful, because it allows to check heterogeneous equality like "does f a matches f b?".

[gwils]

Thanks, I now agree that Eq1 and friends still have reason to exist.
@Ericson2314 did the GHC CI help you with an impact analysis?

[Bodigrim]

along with some laws that canonicity is preserved

Are these laws unconditional or are they expecting that an underlying (==) is lawful? (I'm thinking about instance Ord1 Down issues)

[cgibbard]

This is something I'd also love to see some impact analysis on, but I can imagine most users of the *1 classes being happy about the improvement, even if it might involve knocking out some forgotten instances. I'd also personally be happy about the fixes for Compose. So this is a tentative +1 from me, unless we somehow see that the world would be covered in tiny fires.

[Bodigrim]

I'm tentatively in favor of this proposal, it reflects my experience with *1 classes and QuantifiedContraints. But we really need an impact assessment to understand what we are voting for.

[Bodigrim]

@phadej could you possible please share instructions how to test changes to base against Stackage, as you did in #3 (comment) ?

[phadej]

The canonicity law looks good to me -- I'm actually surprised that Eq1 and co didn't already have something like this. The quantified constraint superclass also looks fine and sensible to me.

The Eq1 class today doesn't have any relationship with Eq, thus stating the liftEq (==) = (==) law is awkward. Quantified super constraint adds necessary bits so the law always type-checks.

the classes are still meaningful if one wants to lift a non-canonical function on the inside. I am not sure how often that is done, but it's theoretically useful enough that I don't feel inspired to rid of this.

E.g. QuickCheck listOf combinator is very much used, it's a special case of liftArbitrary. i also use liftShowsPrec quite a lot to show lists of things which don't (or cannot) have good Show instance (or have bad one).

Are these laws unconditional or are they expecting that an underlying (==) is lawful? (I'm thinking about instance Ord1 Down issues)

I'd say it's fair to assume that (==) :: a -> a -> Bool is lawful. We can say that for every reflexive, transitive f, liftEq f is also reflexive and transitive: That is relaxed version as liftEq f _ _ = True is trivially reflexive and transitive for any f, but otoh it's stricter as liftEq implementation may assume that f is reflexive and transitive.

could you possible please share instructions how to test changes to base against Stackage

I'll try to do that asap. (They aren't complicated, but not entirely trivial). A good starting point is to have a patch applied to a version of GHC and base which has stackage snapshot (e.g. 9.0.1 or 8.10.x). Migrating stackage to ghc-head is too much work.

[Ericson2314]

Thanks for mentioning @phadej that the laws are awkward to have without the superclass. That is an added benefit I forgot.

The MR had a error I think I just figured out --- a test needed to be updated, but it was in the haddock submodule so my git diff missed it. When it rebuilds I think there is a button I can hit to make it do a head.hackage run.

[Ericson2314]

Are these laws unconditional or are they expecting that an underlying (==) is lawful?

I think they need not relay on a sane underlying (==). e.g. [NaN, Nan] :: [Double] should not be equal to itself, right?

In fact,

liftEq f = and . liftA2 f
liftCompare f = foldr thenCmp EQ . liftA2 f

might be valid laws too. But I don't know what the cost of those super-classes would be, and especially thenCmp not being associative, so I rather punt on that until later :).

[phadej]

There are also wrappers in other core-ish libraries, e.g. Reverse and Backwards:

• https://hackage.haskell.org/package/transformers-0.6.0.2/docs/Data-Functor-Reverse.html
• https://hackage.haskell.org/package/transformers-0.6.0.2/docs/Control-Applicative-Backwards.html

Would be nice if instances were uniform for these.

[phadej]

Does this proposal break or not code like:

class Eq1 t => Hashable1 t where ...
instance (Hashable1 f, Hashable1 g) => Hashable1 (Compose f g) where ...

I have to think about this, so probably a good idea to explicitly write the answer down in the proposal.