Generic selections of subexpressions

Tools for computer languages need position information: compilers for providing better error messages, structure editors for mapping between structural and textual views, and debuggers for navigating through a term, for instance. Manually adding position information to an abstract syntax tree is tedious and requires pervasive changes: the original tree becomes verbose and every function operating on it needs to be adapted. In this paper, we describe how to automatically extend datatypes with position information using datatype-generic programming techniques. Furthermore, we show examples of how to use this position information: parsers that automatically construct trees annotated with positions, catamorphisms that deal with failure by reporting error locations, and zippers that efficiently navigate annotated trees. The generic programming technique we describe is applicable to a wide range of domains.