Data types à la carte

Abstract

📜 Abstract

This paper describes a technique for assembling both data types and functions from isolated individual components. We also explore how the same technology can be used to combine free monads and, as a result, structure Haskell’s monolithic IO monad.

Description

✨ Summary

The paper presents a modular approach to the expression problem in Haskell. Recursive data types are represented as fixed points of functors, while individual constructors are isolated as functorial signatures. These signatures can be combined with coproducts, allowing new language constructs to be added without modifying existing datatype definitions or functions.

Functions over the resulting open datatypes are defined compositionally. Type classes provide separate algebras for individual signatures, and coproduct instances combine those algebras. A generic fold then traverses the complete recursive structure. Type-class-based injections and smart constructors hide the representation details of coproducts, while partial projections support modular pattern matching and transformations. The paper demonstrates the approach with arithmetic expressions, evaluation, pretty-printing, and distributivity-based rewriting.

The same construction is applied to free monads. Effect operations are represented as functors, combined through coproducts, and interpreted using folds. This provides a typed representation of effect capabilities: a term’s type records which operations it may use. The technique is illustrated with calculator state operations and with a decomposition of selected input/output operations, such as terminal and filesystem effects, instead of placing all effects in a single undifferentiated IO monad.

The approach is limited to structures that can be represented using the proposed functorial and free-monad encodings. The original implementation also relies on overlapping and other non-Haskell-98 type-class extensions, and more complex datatypes, binders, GADTs, and nested datatypes require further machinery.

The approach was subsequently used as a basis for modular compiler construction: Day and Hutton explicitly applied it to modular syntax and semantics for languages with separate computational effects. (researchgate.net) Bahr and Hvitved extended the technique into compositional data types, including support for variable binders through parametric higher-order abstract syntax. (arxiv.org) The Haskell compdata library operationalized these ideas for type-safe construction, transformation, and analysis of abstract syntax trees. (stackage.org) Later work on scoped and intrinsically typed language representations continued to cite the paper as a foundation for combining modular syntax with free-monad and type-level techniques. (arxiv.org) Cambridge’s citation record currently lists more than 200 citations, indicating substantial continuing research influence. (cambridge.org)