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.
CodePudding user response:
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.