Go home now Header Background Image
Search
Submission Procedure
share: |
 
Follow us
 
 
 
 
Volume 23 / Issue 1

available in:   PDF (137 kB) PS (226 kB)
 
get:  
Similar Docs BibTeX   Write a comment
  
get:  
Links into Future

 

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