For a long time I’ve noticed that there’s a lot of persistent confusion about the differences and similarities between module systems (as seen in languages like OCaml) and typeclasses (as seen in languages like Haskell or Rust). This is an attempt to clear up the confusion.
The main goal of typeclasses as a language construct is to provide ad-hoc polymorphism. This is also known as operator overloading or type-based dispatch. The main point of ad-hoc polymorphism is as a convenience feature for programming in the small: it lets you reuse the same identifiers across types. For example, I might want to use the + symbol to denote both addition on integers and addition on vectors of floats (Importantly the vector type might be defined in a random library, so we can’t hardcode this behaviour in the language).
The main goal of module systems as a language construct is to provide modular abstraction. Some parts of this feature have names in the broader software industry, like dependency injection, encapsulation, and information hiding. The main point of modular abstraction is to enable more efficient programming in the large, by allowing you to express your program decomposition explicitly. It gives you a compositional way to break down programs into component pieces recursively.
The main factors that I think lead to confusion are:
However, while emulation is possible in many cases it’s usually not optimal.
The motivational idea behind typeclasses is basically, if you’re going to overload a symbol, it should “morally” mean the same thing. For example the symbol + denotes the abstract idea of addition, and we can have different implementations for different types. This is in contrast to for example C++ where << can mean bitshift or stream redirection depending on the type, which have nothing in common. The goal here is for the meaning of programs to be easier to understand (relative to the unprincipled C++ thing), while reducing cognitive overhead by reducing the number of symbols. We can learn a few symbols that work with abstract structures, like + or >>=, and use them across a variety of different concrete structures.
If we want to be a bit more serious about this we need to consider the semantics as well. How do we make sure + does in fact denote an abstract addition operation? Well, we can add laws to the typeclass. For instance we can say that addition has to satisfy (though this isn’t true for floats), and then check that new implementations do in fact satisfy the law using a property test or a proof witness. In general, each typeclass can be bundled with some description of semantics, ideally machine checked in the form of a test suite or proof obligation.
For taste, here is the definition of the Num typeclass in Haskell, taken from ghc. Notice that it gives some laws, but in this case they are only customary. For instance, floating point multiplication is not associative but it still has a Num instance.
-- | Basic numeric class.
--
-- The Haskell Report defines no laws for 'Num'. However, @('+')@ and @('*')@ are
-- customarily expected to define a ring and have the following properties:
--
-- [__Associativity of @('+')@__]: @(x + y) + z@ = @x + (y + z)@
-- [__Commutativity of @('+')@__]: @x + y@ = @y + x@
-- [__@'fromInteger' 0@ is the additive identity__]: @x + fromInteger 0@ = @x@
-- [__'negate' gives the additive inverse__]: @x + negate x@ = @fromInteger 0@
-- [__Associativity of @('*')@__]: @(x * y) * z@ = @x * (y * z)@
-- [__@'fromInteger' 1@ is the multiplicative identity__]:
-- @x * fromInteger 1@ = @x@ and @fromInteger 1 * x@ = @x@
-- [__Distributivity of @('*')@ with respect to @('+')@__]:
-- @a * (b + c)@ = @(a * b) + (a * c)@ and @(b + c) * a@ = @(b * a) + (c * a)@
-- [__Coherence with 'toInteger'__]: if the type also implements 'GHC.Real.Integral', then
-- 'fromInteger' is a left inverse for 'GHC.Internal.Real.toInteger', i.e. @fromInteger (toInteger i) == i@
class Num a where
(+), (-), (*) :: a -> a -> a
-- | Unary negation.
negate :: a -> a
-- | Absolute value.
abs :: a -> a
-- | Sign of a number.
-- The functions 'abs' and 'signum' should satisfy the law:
--
-- > abs x * signum x == x
--
-- For real numbers, the 'signum' is either @-1@ (negative), @0@ (zero)
-- or @1@ (positive).
signum :: a -> a
-- | Conversion from an 'Integer'.
-- An integer literal represents the application of the function
-- 'fromInteger' to the appropriate value of type 'Integer',
-- so such literals have type @('Num' a) => a@.
fromInteger :: Integer -> a
x - y = x + negate y
negate x = 0 - xThe point of modules is to allow you to ergonomically abstract over parts of your program. To do that, we split the program up into parts (“modules”, “structures”), and then explicitly specify how they slot together. Importantly, we can reduce the total effort to reason about the full program by making each module hide parts of itself (encapsulation!) from other modules that interact with it.
That’s good for outputs, but we also have to consider abstracting over inputs. To do that, we can make parametrized modules (these are often called functors for historical reasons) that are not modules but can become a module when instantiated with some other module(s). Which modules are we allowed to instantiate with? All the modules that conform to a particular interface (which are often called signatures in the literature)!
Again, if we’re being serious about this we might attach some semantics to the interface, such as customary laws, a test suite or a proof obligation. After all, one of the most common reasons to structure your program with a modular decomposition is to increase ease of testing. Identifying important interfaces and testing at the interface is a quite effective way to get a lot of coverage for cheap.
Let’s go through an example that uses many features. I have taken the following code from the unison file synchronization project.
First, we declare that we have a StringMap type which conforms to the Map.S signature from the standard library, but with the key type specialized to String. That means any code that depends on the interface the stdlib exposes can use our custom map, and it’ll even check that all callsites have the correct key type.
Next we have a parametrized module. The high level idea is that this is an interface that abstracts over platform-specific apis for file watching.
watch handle typeS that exposes an api for working with watchersF.F
FS (since the parametrized module returns something with an empty signature, it can only be used for its side-effects.)module StringMap : Map.S with type key = string
module F (M : sig type watch end) : sig
type t
val get_id : t -> int
val get_watch : t -> M.watch option
val set_watch : t -> M.watch option -> unit
val get_subdirs : t -> t StringMap.t
val is_root : t -> bool
val file_by_id : (int, t) Hashtbl.t
val dir_path : t -> string -> string
val signal_change :
float -> t -> string option -> [> `CREAT | `DEL ] -> unit
val signal_overflow : unit -> unit
module type S = sig
val add_watch : string -> t -> bool -> unit
val release_watch : t -> unit
val watch : unit -> unit
val clear_event_memory : unit -> unit
end
module F (M : S) : sig end
endTypeclasses are often used for abstraction. For example, here’s some simple code from a project of mine:
pub trait FileSystem {
/// Check if a path exists
fn exists(&self, path: &Path) -> bool;
/// Get the file type of a path
/// Returns an error if the path doesn't exist or can't be accessed
/// Note: follows symlinks, so a symlink to a directory will return FileType::Dir
fn file_type(&self, path: &Path) -> Result<FileType>;
/// List entries in a directory
/// Returns an iterator of (name, file_type) pairs
/// Note: follows symlinks, so a symlink to a directory will return FileType::Dir
fn read_dir(&self, path: &Path) -> Result<impl Iterator<Item = Result<(OsString, FileType)>>>;
/// Read the contents of a file as a string
fn read_to_string(&self, path: &Path) -> Result<String>;
}Since I don’t need many filesystem operations, I only declare the ones I need, which makes it tractable to test at that interface easily.
What have we lost relative to using modules instead?
read_dir may return something that satisfies the Iterator trait with a specialized Item type. But I can’t express “this method returns something that matches this particular signature” (i.e inline interfaces aren’t a thing). All interfaces must be tied to some type (which exist in a scope) and can’t be nested.impl blocks but they’re also not composable).foo.bar() has to first infer the type of foo, then look at everything that might transitively impl foo, then see what possible implementations for bar there are)In general, I think this approach promotes what I call a “set of functions” approach to program decomposition. The typeclass worldview is that there is a global type database, and functions may see different parts of this database depending on scoping, but ultimately the program is just a set of functions. Each function stands alone and you have to reason at the function level.
Modules give us a richer way to think about program decomposition. We’re not limited to drawing the boundaries at functions. We can reason about larger parts of our program at once. In terms of the earlier analogy, modules let us think in terms of nontrivial subsets of the program at a time.
Well there’s one thing left, which is going the other way.
Many ML programmers will say “you don’t need ad-hoc polymorphism, and maybe it’s bad actually”. This isn’t as unreasonable an argument as it sounds: with careful use of lexically scoped imports, the lack of ad-hoc polymorphism is only slightly more verbose, and is probably more mechanically easy to understand. Plus since everything is explicit, the compiler doesn’t have to do any search to resolve polymorphic operations, which speeds up compilation. I think part of the appeal of Zig over Rust for many Zig users is because Zig programmers tend to fall on that side of the fence as well.
All of that is a long way to say that at least in OCaml, the way to achieve ad-hoc polymorphism is to simply not have it. For example here is some code from Real World OCaml that illustrates some ways to use Int64 arithmetic without having to namespace every arithmetic operation.
let average x y =
let open Int64 in
(x + y) / of_int 2;;
let average x y =
Int64.((x + y) / of_int 2);;Let’s say we really want ad-hoc polymorphism. If we think about it, traditional typeclasses can be expressed in terms of modules in the following way:
And then, whenever we use something from a signature, we infer the type and then lookup the concrete module using it.
In theory, you could implement ad-hoc polymorphism pretty much the exact same way as the typeclass-first approach like this, with no real loss in ergonomics. This is basically what the Modular Implicits proposal for OCaml suggests.
Scala 3 also supports what it calls “Contextual Abstraction”, which is essentially a way of doing the above. The main difference with more traditional typeclass systems is that it doesn’t require coherence which is something out of the scope of this post.
Yes! Haskell has the Backpack module system that nobody uses, in addition to the typeclass system everybody uses. In theory, it has good support for both modular abstraction and ad-hoc polymorphism. Unfortunately, Backpack came kind of late to the ecosystem and has not seen much adoption.
I believe Rocq (formerly Coq) also has independent module and typeclass systems.
Rust has a module system separate from its trait system, but it’s too weak to support full modular programming. The module system only supports encapsulation and has no way to specify abstract module signatures, and therefore can’t have parametrized modules.
Please remember the distinction between modular abstraction and ad-hoc polymorphism. They can both be useful features in a programming language, and they have different concerns: one is for programming in the large, and the other in the small. Typeclasses and Modules are simply means to those ends.
If you’re designing a new language, I think a lot of people reach for typeclasses and good support for ad-hoc polymorphism first, with modular abstraction an afterthought. I personally think that is backwards: I find, in practice, good support for modular abstraction more valuable than ad-hoc polymorphism for writing high quality programs.