Why are instances matched only by their heads?

Question

I'll start by introducing a concrete problem (StackOverflow guys like that). Say you define a simple type

data T a = T a

This type is a Functor, Applicative and a Monad. Ignoring automatic deriving, to get those instances you have to write each one of them, even though Monad implies Applicative, which implies Functor. More than that, I could define a class like this

class Wrapper f where
    wrap   :: a -> f a
    unwrap :: f a -> a

This is a pretty strong condition and it definitely implies Monad, but I can't write

instance Wrapper f => Monad f where
    return = wrap
    fa >>= f = f $ unwrap fa

because this, for some reason, means "everything is a Monad (every f), only if it's a Wrapper", instead of "everything that's a Wrapper is a Monad".

Similarly you can't define the Monad a => Applicative a and Applicative a => Functor a instances.

Another thing you can't do (which is only probably related, I really don't know) is have one class be a superclass of another one, and provide a default implementation of the subclass. Sure, it's great that class Applicative a => Monad a, but it's much less great that I still have to define the Applicative instance before I can define the Monad one.

This isn't a rant. I wrote a lot because otherwise this would quickly the marked as "too broad" or "unclear". The question boils down to the title. I know (at least I'm pretty sure) that there is some theoretical reason for this, so I'm wondering what exactly are the benefits here.

As a sub question, I would like to ask if there are viable alternatives that still keep all (or most) of those advantages, but allow what I wrote.

Addition: I suspect one of the answers might be something along the lines "What if my type is a Wrapper, but I don't want to use the Monad instance that that implies?". To this I ask, why couldn't the compiler just pick the most specific one? If there is an instance Monad MyType, surely it's more specific than instance Wrapper a => Monad a.

Answer 1

There's a lot of questions rolled into one here. But let's take them one at a time.

First: why doesn't the compiler look at instance contexts when choosing which instance to use? This is to keep instance search efficient. If you require the compiler to consider only instances whose instance heads are satisfied, you essentially end up requiring your compiler to do back-tracking search among all possible instances, at which point you have implemented 90% of Prolog. If, on the other hand, you take the stance (as Haskell does) that you look only at instance heads when choosing which instance to use, and then simply enforce the instance context, there is no backtracking: at every moment, there is only one choice you can make.

Next: why can't you have one class be a superclass of another one, and provide a default implementation of the subclass? There is no fundamental reason for this restriction, so GHC offers this feature as an extension. You could write something like this:

{-# LANGUAGE DefaultSignatures #-}
class Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

    default pure :: Monad f => a -> f a
    default (<*>) :: Monad f => f (a -> b) -> f a -> f b
    pure = return
    (<*>) = ap

Then once you had provided an instance Monad M where ..., you could simply write instance Applicative M with no where clause and have it Just Work. I don't really know why this wasn't done in the standard library.

Last: why can't the compiler allow many instances and just pick the most specific one? The answer to this one is sort of a mix of the previous two: there are very good fundamental reasons this doesn't work well, yet GHC nevertheless offers an extension that does it. The fundamental reason this doesn't work well is that the most specific instance for a given value can't be known before runtime. GHC's answer to this is, for polymorphic values, to pick the most specific one compatible with the full polymorphism available. If later that thing thing gets monomorphised, well, too bad for you. The result of this is that some functions may operate on some data with one instance and others may operate on that same data with another instance; this can lead to very subtle bugs. If after all this discussion you still think that's a good idea, and refuse to learn from the mistakes of others, you can turn on IncoherentInstances.

I think that covers all the questions.

Answer 2

Consistency and separate compilation.

If we have two instances whose heads both match, but have different constraints, say:

-- File: Foo.hs

instance Monad m => Applicative m
instance            Applicative Foo

Then either this is valid code producing an Applicative instance for Foo, or it's an error producing two different Applicative instances for Foo. Which one it is depends on whether a monad instance exists for Foo. That's a problem, because it's difficult to guarantee that knowledge about whether Monad Foo holds will make it to the compiler when it's compiling this module.

A different module (say Bar.hs) may produce a Monad instance for Foo. If Foo.hs doesn't import that module (even indirectly), then how is the compiler to know? Worse, we can change whether this is an error or a valid definition by changing whether we later include Bar.hs in the final program or not!

For this to work, we'd need to know that all instances that exist in the final compiled program are visible in every module, which leads to the conclusion that every module is a dependency of every other module regardless of whether the module actually imports the other. You'd have to go quite far along the path to requiring whole-program-analysis to support such a system, which makes distributing pre-compiled libraries difficult to impossible.

The only way to avoid this is to never have GHC make decisions based on negative information. You can't choose an instance based on the non-existence of another instance.

This means that the constraints on an instance have to be ignored for instance resolution. You need to select an instance regardless of whether the constraints hold; if that leaves more than one possibly-applicable instance, then you would need negative information (namely that all but one of them require constraints that do not hold) to accept the code as valid.

If you have only one instance that's even a candidate, and you can't see a proof of its constraints, you can accept the code by just passing the constraints on to where the instance is used (we can rely on getting this information to other modules, because they'll have to import this one, even if only indirectly); if those positions can't see a required instance either, then they'll generate an appropriate error about an unsatisfied constraint.

So by ignoring the constraints, we ensure that a compiler can make correct decisions about instances even by only knowing about other modules that it imports (transitively); it doesn't have to know about everything that's defined in every other module in order to know which constraints do not hold.