Almost all programming languages have some kind of record data structure. While the theory is fairly well understood (they are labeled products, which can be considered open or closed depending on one’s typing rules), the pragmatics are still hotly debated. This is especially apparent in Haskell, where the community generally agrees that its record system is poor while emphatically disagreeing on a better solution. Exploring this design space through concrete implementations is thus quite important.

One of the principal features missing from Haskell’s record system is extensibility of records. Currently, every label used in a record must be unique (within a module), which is generally recognized as problematic. Unlike in the OCaml language, Haskell does not use row typing for its records. Many people have noticed that this could be implemented in Haskell now, using its class system. The downside is that record look-up then becomes linear in the number of labels of that record.

The authors of this paper point out that the label information for records is available at compile time, thus providing an opportunity for compile-time computations to optimize the look-up process.

What is then presented is a beautiful application of staging, the process of cleanly separating compile-time computations from runtime computations. The authors show that with rather clever type class-level programming, one can indeed implement extensible records in Haskell, with good efficiency properties.

While the English in this paper is somewhat awkward throughout, the technical material is of high quality, and is well motivated and presented. Unfortunately for the authors, Haskell is a quickly evolving language, and several new features of the Glasgow Haskell Compiler (GHC) may well render their technical solution suboptimal.

Nevertheless, the fundamental techniques that they apply are sound and worth knowing, even if some of the implementation details will likely have to evolve.