Is this type-class constraint necessary or redundant?

Question

The following code successfully compiles, but gets a warning when using GHC 9.2.3 with -Wredundant-constraints:

{-# LANGUAGE UndecidableInstances, FlexibleInstances #-}

class Functor f => C f where c :: f Int

instance (Functor f, Applicative f) => C f where c = pure 42

The resulting warning:

test.hs:5:10: warning: [-Wredundant-constraints]
    • Redundant constraint: Functor f
    • In the instance declaration for ‘C f’
  |
5 | instance (Functor f, Applicative f) => C f where c = pure 42
  |          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

However, if I remove this constraint, the code no longer type checks:

test.hs:5:10: error:
    • Could not deduce (Functor f)
        arising from the superclasses of an instance declaration
      from the context: Applicative f
        bound by the instance declaration at test.hs:5:10-29
      Possible fix:
        add (Functor f) to the context of the instance declaration
    • In the instance declaration for ‘C f’
  |
5 | instance Applicative f => C f where c = pure 42
  |          ^^^^^^^^^^^^^^^^^^^^

This confuses me.

Is this constraint truly redundant, or is it in fact necessary?

Intuitively I would say that it is redundant, as it is implied by Applicative f already! But GHC begs to differ so I'm unsure.

user_7203016 · Answer

So, the Functor f looks redundant, but it is needed to avoid a problem with recursive superclasses leading to a dictionary containing a superclass field that is actually bottom (i.e., an infinite loop at runtime when the superclass is implicitly accessed).

There is an explanation in the compiler source compiler/GHC/Tc/TyCl/Instance.hs, in the section titled "Recursive superclasses". The upshot is that when resolving the superclass Functor f for the instance C f, GHC isn't allowed to use Applicative f to resolve Functor f because Applicative f isn't a "smaller dictionary" (see below) than C f. By requiring that superclasses be resolved only through a chain of ever-smaller dictionaries, GHC can ensure that superclass resolution terminates.

In contrast, no Functor f is needed in the instance definition for this similar example:

class Functor f => C f x
instance (Applicative f) => C f Int

because Applicative f is a smaller dictionary than C f Int, so GHC is allowed to use it.

"Smaller dictionary" here is used in a particular technical sense. The size of a dictionary is the number of constructors and variables in its type. So, Applicative f is of size 2, while C f Int is of size 3.

This means that Functor f isn't actually redundant and so the warning is wrong. Issuing the warning looks like a GHC bug.

Is this type-class constraint necessary or redundant?

1 Answers