Trees that Grow

Shayan Najd (The University of Edinburgh, United Kingdom)

Simon Peyton Jones (Microsoft Research, United Kingdom)

Abstract: We study the notion of extensibility in functional data types, as a new approach to the problem of decorating abstract syntax trees with additional information. We observed the need for such extensibility while redesigning the data types representing Haskell abstract syntax inside Glasgow Haskell Compiler (GHC).

Specifically, we describe a programming idiom that exploits type-level functions to allow a particular form of extensibility. The approach scales to support existentials and generalised algebraic data types, and we can use pattern synonyms to make it convenient in practice.

Keywords: Haskell, algebraic data types, expression problem, extensible data types, functional programming, open data types, pattern matching, tree decoration tree annotation

Categories: D.1.1, D.2.13, D.3.2, D.3.3