Are there any good use cases for OverlappingInstances?

Question

I'm designing a library that would greatly benefit from the use of the OverlappingInstances compiler flag. But everyone talks smack about this extension and warns of its dangers. My question is, are there examples of a good use of this extension anywhere on hackage? Is there any rule of thumb on how to encapsulate the badness and use the extension properly?

Answer 1

Perhaps a thought experiment will de-mystify this extension a bit.

Let's pretend that we've dropped the restriction that functions defined with multiple pattern cases must be all in one place, so that you can write foo ("bar", Nothing) = ... at the top of a module, and then have cases like foo ("baz", Just x) = ... elsewhere. In fact, let's go even further, and allow cases to be defined in different modules entirely!

If you think that sounds like it would be confusing and error-prone to use, you're correct.

To recover some semblance of sanity, we could add some limitations. For instance (ha, ha), we could require the following properties to hold:

• Anywhere such a function is used, the arguments given must match exactly one pattern. Anything else is a compiler error.
• Adding new patterns (including by importing another module) should never change the meaning of valid code--either the same patterns are chosen, or a compiler error is produced.

It should be clear that matching simple constructors like True or Nothing is straightforward. We also can handwave things a bit and assume that the compiler can disambiguate literals, like "bar" and "baz" above.

On the other hand, binding arguments with patterns like (x, Just y) becomes awkward--writing such a pattern means giving up the ability to write patterns like (True, _) or (False, Just "foobar") later, since that would create ambiguity. Worse yet, pattern guards become nearly useless, because they need very general matches. Many common idioms will produce endless ambiguity headaches, and of course writing a "default" fall-through pattern is completely impossible.

This is roughly the situation with type class instances.

We could regain some expressive power by relaxing the required properties as such:

• Anywhere such a function is used, it must match at least one pattern. No matches is a compiler error.
• If a function is used such that multiple patterns match, the most specific pattern will be used. If there is no unique most specific pattern, an error is produced.
• If a function is used in a way that matches a general instance, but could be applied at run-time to arguments that would match a more specific instance, this is a compiler error.

Note that we are now in a situation where merely importing a module can change the behavior of a function, by bringing into scope a new, more specific pattern. Things might get murky in complicated cases involving higher-order functions, as well. Still, in many cases problems are unlikely--say, defining a generic fall-through pattern in a library, while letting client code add specific cases if needed.

That's roughly where OverlappingInstances puts you. As suggested in the example above, if creating new overlaps is always either impossible or desired, and different modules won't end up seeing different, conflicting instances, then it's probably fine.

What it really comes down to is that the limitations removed by OverlappingInstances are there to make using type classes behave sensibly under the "open world" assumption that any possible instance could later be added. By relaxing those requirements, you're taking on that burden yourself; so think through all the ways that new instances could be added and whether any of those scenarios are a significant problem. If you're convinced that nothing will break even in obscure and devious corner cases, then go ahead and use the extension.

Answer 2

Most people request overlapping instances because they want constraint-directed inference instead of type-directed inference. Type classes were made for type-directed inference and Haskell does not provide an elegant solution to constraint-directed inference.

However, you can still "encapsulate the goodness" by using newtypes. Given the following instance definition which is prone to overlapping instances:

instance (SomeConstraint a) => SomeClass a where ...

You can instead use:

newtype N a = N { unN :: a }

instance (SomeConstraint a) => SomeClass (N a) where ...

Now Haskell's type-class system has a proper specific type to match on (i.e. N a), instead of matching gratuitously on every single type. This lets you control the scope of the instance since only things wrapped in the N newtype will now match.

Answer 3

OverlappingInstances allows you to write many useful things otherwise unimplementable at the typeclass level, the vast majority of these though can be reorganized to use a single functional dependency (written here in kind polymorphic style)

class TypeEq (a :: k) (b :: k) (t :: Bool) | a b -> t where
  typeEq :: Proxy a -> Proxy b -> HBool t

this can currently only be implemented (in a fully generic way) with OverlappingInstance. Examples of use cases include Oleg's encoding of OOP into Haskell. Thus, my one example of a good use of OverlappingInstances is this implementation of TypeEq from the classic HList paper

This particular functionality could be provided very trivially with compiler support (and even work at the type function rather than the fundep level) and thus sticking a single module with TypeEq somewhere does not seem so bad to me.

When I am engaged in dangerous typeclass hackery, I often find the IncoherentInstances behavior (pick the first matching instance) is easier to reason about and more flexible, and so use that at least in the explorative phases of a design. Once I have something that does what I want I try to get rid of extensions, paying particular attention to the less well behaved ones (like these).