Programming Language Theory
Typeclasses and Traits
In 1989, the designers of Haskell debated: how do we write a `sort` function that works for any ordered type - without requiring a common superclass? The answer was typeclasses. Thirty years later, Rust copied the idea as traits - and the entire Rust ecosystem runs on them.
- **Rust serde**: the serialization library works with any type through `Serialize`/`Deserialize` traits - without a single line of library code for user-defined types
- **Haskell lens**: optics are built through `Functor`, `Applicative`, `Monad` typeclasses - enabling code that works with any data structure without a common superclass
- **Rust async**: `Future`, `Stream`, `AsyncRead` - all async abstractions in Rust are traits, making different runtimes (tokio, async-std) interchangeable
Haskell Typeclasses
In 1989, the designers of Haskell faced a puzzle: the function `(+)` must work for `Int`, `Float`, and `Double`, but static typing won't allow a single type signature without sacrificing precision. The solution was **typeclasses** - a mechanism for ad-hoc polymorphism where a class declares an interface and an `instance` implements it for a specific type. These are nothing like OOP classes: a typeclass is a set of function signatures that a type promises to implement.
The key difference from OOP interfaces: a typeclass instance is defined **separately** from the type itself. A new typeclass can be added to an already-existing type - even one from a third-party library - as long as coherence rules are respected.
The class `Functor` is defined as `class Functor f where { fmap :: (a -> b) -> f a -> f b }`. What does the constraint `Functor f` mean in a function signature?
Rust Traits
Rust borrowed the typeclass idea and wired it into the ownership system. A **trait** is a set of methods (and associated types) that a type must implement. Unlike Haskell where typeclasses only affect type-checking, Rust traits participate in borrow checking and lifetime analysis. Trait objects (`dyn Trait`) give dynamic dispatch; `impl Trait` in return position gives static dispatch without exposing the concrete type.
Rust traits come in three dispatch flavors: **static** (monomorphization via generics - zero runtime cost), **dynamic** (`dyn Trait` - vtable, pointer indirection) and **impl Trait** (static without type exposure, useful for returning closures).
What is the key difference between `fn f<T: Display>(x: T)` and `fn f(x: &dyn Display)` in Rust?
Coherence
**Coherence** is the guarantee that for any (type, trait/class) pair there exists at most one instance. Without this, `show (1 :: Int)` could produce different results depending on import order - a catastrophe for static typing. Both Haskell and Rust impose strict rules about where instances may be defined to preserve this invariant.
Violations of coherence are called **overlapping instances** in Haskell or **conflicting implementations** in Rust. Haskell has the `OverlappingInstances` and `IncoherentInstances` extensions, but they are considered dangerous - they undermine the predictability of type inference.
Why can't a Haskell program have two `Show Int` instances simultaneously?
Orphan Rules
The **orphan rule**: an instance of a trait/class may only be defined in the crate/module that defines **either the type or the trait**. Writing `impl Display for Vec<i32>` in a custom crate is rejected because `Display` (from `std::fmt`) and `Vec` (from `std::vec`) are both foreign. An instance is called an 'orphan' when it belongs to neither home.
The standard workaround for the orphan rule in Rust is the **newtype** pattern: `struct Wrapper(Vec<i32>)`. This is a local type, so `impl Display for Wrapper` is legal. The cost: unwrapping via `.0` or implementing `Deref`.
Rust traits and Haskell typeclasses are just interfaces, like in Java or C#
The key difference: an instance is defined separately from the type and can be added after the fact. In Java an interface must be declared at class definition - retroactive extension is impossible without modifying source.
Retroactivity is precisely what makes typeclasses more powerful than OOP interfaces: a new trait can be added to a foreign type (within orphan rule limits) without touching its source code.
A crate `my_crate` wants to implement `serde::Serialize` (from `serde`) for `chrono::DateTime` (from `chrono`). What will happen?
Key ideas
- **Typeclasses / traits** are ad-hoc polymorphism: one function name, different implementations per type, selection at compile time
- **Coherence** guarantees at most one instance per (type, trait) pair - making type inference deterministic and predictable
- **Orphan rule** forbids defining an instance outside the module of the type or trait - worked around via the newtype pattern
Related topics
Typeclasses and traits are the foundation for more advanced type system mechanisms:
- Algebraic Data Types — ADTs + typeclasses = expressiveness without inheritance; typeclasses describe behavior, ADTs describe structure
- Dependent Types — Some languages (Idris, Lean) implement interfaces through dependent types, which are even more powerful than typeclasses
Вопросы для размышления
- Why is the newtype pattern in Rust a deliberate language-level tradeoff rather than a design flaw?
- If coherence were removed from Haskell, what specifically would break in type inference?
- How does retroactive type extension via traits fundamentally differ from monkey-patching in Ruby or JavaScript?
Связанные уроки
- plt-07-algebraic-types — Most typeclasses are instantiated over ADTs; you need to know the shapes before defining behavior on them
- plt-08-generics — Higher-kinded types enable Functor/Monad; generics are a prerequisite for HKT
- plt-12-subtyping — Typeclasses (ad-hoc polymorphism) vs subtype polymorphism are two competing models for polymorphic dispatch
- plt-19-oop-theory — OOP interfaces vs Haskell typeclasses - same goal, different semantics and expressiveness
- ct-02