Understanding Haskell-style Overloading via Open Data and Open Functions

Abstract

We present a new, uniform semantics for Haskell-style overloading. We realize our approach in a new core language, System F${}_{\mathrm{D}}$, whose metatheory we mechanize in the Lean4 interactive theorem prover. System F${}_{\mathrm{D}}$ is distinguished by its open data types and open functions, each given by a collection of instances rather than by a single definition. We show that System F${}_{\mathrm{D}}$ can encode advanced features of Haskell's of type class systems, more expressively than current semantics of these features, and without assuming additional type equality axioms.