osa1 github about atom

Coherence and orphan instance rules

August 29, 2026 - Tagged as: en, haskell, rust, plt.

Typeclasses are an overloading mechanism that allows compile time or runtime polymorphism. A typeclass method call like m a b ... (or a.m(b, ...) in Rust) resolves to a concrete method based on the type arguments passed to the method.

class ToString t where
    toString :: t -> String

instance ToString Bool where
    toString = undefined

instance ToString Int where
    toString = undefined

f = toString (123 :: Int)

g = toString True

toString here is overloaded: the two calls to the same method actually call different concrete methods.

These type arguments are commonly based on the arguments or the return value (which is inferred from the call site context).

class Convertible a b where
  convert :: a -> b

instance Convertible Int String where
  convert = show

instance Convertible Int Bool where
  convert = (/= 0)

f :: Bool
f = convert (123 :: Int) -- actual method called depends on the return type

When a typeclass type parameter is not used in a method signature, the compiler has no way of choosing the instance, so we have to specify the type arguments explicitly:

{-# LANGUAGE AllowAmbiguousTypes #-}

class Ambiguous a b where
  weird :: a -> IO ()

instance Ambiguous Int Bool where
  weird _ = putStrLn "First instance"

instance Ambiguous Int String where
  weird _ = putStrLn "Second instance"

f :: IO ()
f = weird @Int @Bool (123 :: Int)

Here f calls Ambiguous Int Bool’s weird, based on the explicit type arguments. Without the type arguments the compiler has no way of knowing which weird to call.

Crucially, instances are not first-class values and they’re not named. This allows maintaining a useful property that we want to have when working with typeclasses: if we call the same method with the same type parameters in different parts of a program, they should all call the same method. This is absolutely essential, and if you’ve programmed with Rust’s traits or Haskell’s typeclasses even for a short while, you inevitably wrote code that assumes this property.

Some of the common cases where we rely on this property is:

This property is called coherence.

(If you’re familiar with OOP with subtyping, coherence exists in OOP languages as x.m() calling the same method m for the same type of x, everywhere in the program.)

More formally, coherence says that for any constraint C type1 ... typeN, there can be at most one instance that matches the constraint. So if a method call generates the constraint, we know that there’ll be at most one instance that matches the constraint, and it’s the method of that instance that will be called.

When there are multiple instances that can potentially match the same constraint, they’re called overlapping instances. Overlapping instances are how we get an incoherent system.

An important fact about coherence is that it’s a global (or whole-program) property. Without globally saying that a constraint can resolve to at most one instance, there can be different parts of the program (maybe different libraries, modules) where e.g. Hash String resolves to different instances, and invalidate our data structure invariants.

(In OOP terms, you can think of this as x.hashCode() returning different values in different parts of the program, for the identical x, and with no mutation on x in between.)

Here’s an example where the modules are coherent, but the main module importing the others is not:

-- C.hs
class C a b

-- A.hs
import C
data A = A
instance C A b

-- B.hs
import C
data B = B
instance C a B

-- Main.hs
import C
import A
import B

test :: C p q => p -> q -> IO ()
test _ _ = pure ()

main = test A B

Here A and B are both individually coherent, but Main is not, despite the fact that it’s not defining any instances. In Main, C A B is matched by both of the instances imported.

Coherence being a global property poses a challenge. We want libraries that compose. If we accept two libraries (like A and B above) as type-safe and coherent, then we should be able to import them in a third one and the system should still be coherent. Otherwise, if we also consider transitive dependencies, it creates a fragmented ecosystem of libraries where many libraries can’t be used in the same program (directly or transitively).

This is ensured with orphan instance rules. These rules limit where we can define an instance, with the goal of making sure coherent libraries can be composed.

For the purposes of this blog post, the exact rules are not important (and they also depend on the language). However just as an example, if we had a single-parameter version of our C above and a type in another library:

-- C.hs
class C a

-- A.hs
data A = A

Orphan instance rules dictate that the only place where instance C A can go is in A.hs. So there can’t be two modules that define instance C A that can be imported in a third one, the instance can only come from A.

What about the two-parameter version class C a b? What would be the rules of where to allow instances like:

Or, what if we also have higher-kinded type parameters in the class, like Foldable? What if we also had extra type parameters?

Having modular rules to enforce program-wide coherence while also not being too strict (allowing common and useful use cases) is a non-trivial problem. As an example, in Rust, the incoherent Haskell example above is not allowed: the instance instance C a B is disallowed by the orphan instance rules. The details of the rule that disallows this is described in an RFC called “Re-rebalancing coherence”. But note that:

  1. This is a follow-up to an earlier orphan instance rule change “Rebalancing coherence”, which turned out to be too strict.
  2. It’s not entirely obvious (at least to me) that the new rules are sound. I.e. if they allow two instances in two libraries, a third one importing the two won’t be incoherent.

By definition, orphan instance rules need to follow instance resolution (or constraint solving) rules: we want a constraint to resolve to one instance (if it ever does) everywhere in the program. With different instance resolution rules, the orphan rules would have to change too.

However, interestingly, I couldn’t find any formal treatment of orphan instance rules, with proofs that the rules only allow a coherent system and examples of common use cases that they support. I think there’s a language design research opportunity here where we formalize instance resolution rules and orphan instance rules, and prove that the rules only allow a globally coherent system.

There’s a lot more to say about instance resolution and orphan rules, so hopefully more on this topic later. In this post I just wanted to give some definitions that I’ll refer to later.