Extensible Data Types with Ad-Hoc Polymorphism

Abstract

This paper proposes a novel language design that combines extensible data types, implemented through row types and row polymorphism, with ad-hoc polymorphism, implemented through type classes. Our design introduces several new constructs and constraints useful for generic operations over rows. We formalize our design in a source calculus λρ⇒, which elaborates into a target calculus Fω⊗⊕. We prove that the target calculus is type-safe and that the elaboration is sound, thus establishing the soundness of λρ⇒. All proofs are mechanized in the Lean 4 proof assistant. Furthermore, we evaluate our type system using the Brown Benchmark for Table Types, demonstrating the utility of extensible rows with type classes for table types.