Scala

Scala’s Implicits: Porting Haskell’s Type Classes Into a Language That Already Had Subtyping

Philip Wadler invented a coherent mechanism in 1988. Thirty-one years later, he co-authored a paper trying to get some of that coherence back.

Type classes are one of the rare programming language features with a clean origin story: one paper, one design, one well-defined property it was built to preserve. Scala’s implicits reuse the same core idea, resolving an overloaded operation by the type it’s used at, but Scala arrived at that idea from inside an object-oriented language that already had subtyping, inheritance, and lexical scoping doing other jobs. Porting the mechanism meant deciding what to do when those two designs pulled in different directions, and the answer Scala chose quietly gave up a guarantee Haskell had built the whole thing around.

What Wadler Actually Built in 1988

Philip Wadler and Stephen Blott circulated “How to Make Ad-hoc Polymorphism Less Ad-hoc” in October 1988, later published at POPL in January 1989. Their type classes let a function like (==) be defined once per type, with the compiler resolving which implementation to use, and internally, compiling the whole thing down to ordinary Hindley-Milner code by passing a “dictionary” of the relevant operations as a hidden extra argument. The design leaned on one crucial, largely unstated assumption: for any given type, there is exactly one instance of a given class in scope for the whole program. Haskell never made that a hard syntactic rule, but the compiler and community enforce it socially, GHC warns about “orphan instances” defined somewhere the type or class doesn’t live, specifically because they’re the main way this assumption can break. Every type class method call resolves the same way everywhere in the program. That property has a name in the type-systems literature: coherence.

Scala Borrows the Mechanism, Not the World It Lived In

Scala’s implicit parameters, part of the language since the mid-2000s, let a function ask for an argument the compiler will fill in automatically by searching for a value of the right type, and the community discovered early on, informally, that this was enough to encode Haskell-style type classes without any dedicated syntax. Bruno Oliveira, Adriaan Moors, and Martin Odersky wrote this folklore down properly in a 2010 OOPSLA paper, “Type Classes as Objects and Implicits,” which is also candid that Scala’s version departs from Haskell’s on exactly the point that matters here: instead of resolving against one global, closed table of instances, Scala resolves an implicit parameter by searching a specific, ordered sequence of lexical scopes at the call site.

Years between the original type-class design and the point where its coherence property needed to be explicitly revisited. Sources: Wadler & Blott, POPL 1989; Oliveira, Moors & Odersky, OOPSLA 2010; Schrijvers, Oliveira, Wadler & Marntirosian, JFP 2019.

Seven Places to Look Instead of One

Haskell’s instance table is global: import a module and every instance it defines becomes visible everywhere, permanently, for the rest of compilation. Scala’s compiler instead walks an ordered list of scopes until it finds a match: values defined locally, values explicitly imported, values imported via a wildcard, the companion object of the expected type, the implicit scope of that type’s own type arguments, and finally outer objects for nested types. Where Haskell asks “what is the one instance for this type,” Scala asks “what’s visible from exactly here,” and those are different questions with different answers depending on where “here” is.

Number of distinct places each language’s compiler searches to resolve an instance for a given type. Haskell: one closed, global table. Scala: an ordered sequence of lexical and companion scopes.

The Code That Would Be a Compile Error in Haskell

The consequence is easy to demonstrate and entirely legal Scala:

object AscendingOrder {
  implicit val intOrd: Ordering[Int] = Ordering.Int
}

object DescendingOrder {
  implicit val intOrd: Ordering[Int] = Ordering.Int.reverse
}

object UseAscending {
  import AscendingOrder._
  val sorted = List(3, 1, 2).sorted // ascending
}

object UseDescending {
  import DescendingOrder._
  val sorted = List(3, 1, 2).sorted // descending
}

Both call sites compile without a single warning, and each is locally unambiguous. But the same type, Int, resolves to two different Ordering instances depending purely on which object happens to be imported nearby. In Haskell, defining two Ord Int instances anywhere in the same program is close to a contradiction the whole design tries to rule out. In Scala, it’s a two-line demonstration.

Subtyping Adds a Second Twist: Priority by Inheritance

Scala’s own standard library relies on a second mechanism that has no Haskell counterpart at all: using ordinary class inheritance to break ties between competing implicits. The Predef object, whose members are implicitly available everywhere, is declared as object Predef extends LowPriorityImplicits, and Scala’s official collections documentation explains the effect directly: when two implicit conversions both apply, “implicits in subclasses and subobjects take precedence over implicits in base classes,” so the conversion defined in Predef itself wins over the one inherited from LowPriorityImplicits. That’s subtyping, a feature with no analogue in Haskell’s instance resolution at all, pressed into service as a priority system for an otherwise unrelated mechanism, precisely because implicit search needed some way to pick a winner that a flat, unordered global table never had to.

Wadler Comes Back to Fix It

By 2019, this had become enough of an open problem in the type-systems literature that Philip Wadler himself co-authored a paper about it. “COCHIS: Stable and Coherent Implicits,” with Tom Schrijvers, Bruno Oliveira, and Koar Marntirosian, proposes a redesigned implicit calculus that keeps the flexibility Scala’s local scoping offers, overlapping instances included, while restoring the coherence and stability guarantees the original 1988 design had by construction. It’s a research calculus, not a patch shipped into Scala itself. Scala 3, released in 2021, renamed and restructured the feature into given and using clauses, and its priority and ambiguity rules for resolving competing givens were still being actively reworked by the language’s own designer years after that release. The underlying trade, local lexical scoping in exchange for a coherence guarantee Haskell never had to negotiate away, is unchanged.

What to know before leaning on implicits or givens as type classes

  • Two modules importing different instances for the same type can silently produce different behavior; nothing warns you the way GHC’s orphan-instance messages do
  • Using inheritance to prioritize one implicit over another, the LowPriorityImplicits pattern, is a real technique in Scala’s own standard library, not a code smell unique to user code
  • Scala 3’s given/using syntax is a readability and ergonomics redesign, not a coherence fix; the same local-scope search order still applies
  • If cross-module consistency for a type-class-like instance actually matters, keep exactly one instance per type in its companion object and avoid competing imports, since the language won’t enforce that discipline for you

What We Learned

Wadler’s 1988 type classes worked because Haskell resolves every overloaded call against one global, closed table, so the same type always gets the same instance everywhere. Scala’s implicits reuse the resolution-by-type idea but had to fit it into a language that already had lexical scoping and subtyping doing other work, and the fit came at the cost of that global guarantee: Scala instead searches an ordered sequence of local scopes, which means the same type can legitimately resolve to different instances in different parts of the same program, and inheritance itself gets pressed into service as a tie-breaker with no equivalent on the Haskell side. Thirty-one years after the original paper, one of its own authors co-wrote a calculus specifically aimed at getting that lost coherence back, which is about as clear a signal as the field offers that porting a type system into a new host language changes more than the syntax.

Eleftheria Drosopoulou

Eleftheria is an Experienced Business Analyst with a robust background in the computer software industry. Proficient in Computer Software Training, Digital Marketing, HTML Scripting, and Microsoft Office, they bring a wealth of technical skills to the table. Additionally, she has a love for writing articles on various tech subjects, showcasing a talent for translating complex concepts into accessible content.
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Oldest
Newest Most Voted
Back to top button