Coherence and orphan instance rules

# Coherence and orphan instance rules Source: [https://osa1.net/posts/2026-08-29-coherence-and-orphans.html](https://osa1.net/posts/2026-08-29-coherence-and-orphans.html) **August 29, 2026**\- Tagged as:[en](https://osa1.net/tags/en.html),[haskell](https://osa1.net/tags/haskell.html),[rust](https://osa1.net/tags/rust.html),[plt](https://osa1.net/tags/plt.html)\. 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: - If we log/print a value with an overloaded function, the printed format for the same argument is the same, regardless of where it was printed\. - If we serialize a value in one part of the program \(e\.g\. in library A\) and deserialize it in another part \(e\.g\. in library B\), the serialization and deserialization call sites use the same instance and therefore be compatible in the format they expect\. - For`Hash`and`Ord`based data structures \(e\.g\. hash or ordered maps and sets\), the insertion and lookup sites always use the same hash code function and therefore maintain the data structure invariants and e\.g\. never add duplicate keys etc\. 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: - `instance C A b` - `instance C a B` - `instance C A B` - `instance C \[a\] b` - `instance C a \(Maybe b\)` - … 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”](https://github.com/rust-lang/rfcs/pull/2451)\. But note that: 1. This is a follow\-up to an earlier orphan instance rule change[“Rebalancing coherence”](https://github.com/rust-lang/rfcs/pull/1023), 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\.