Higher inductive types are inductive types that include nontrivial higher-dimensional structure, represented as identifications that are not reflexivity. While work proceeds on type theories with a computational interpretation of univalence and higher inductive types, it is convenient to encode these structures in more traditional type theories with mature implementations. However, these encodings involve a great deal of error-prone additional syntax. We present a library that uses Agda’s metaprogramming facilities to automate this process, allowing higher inductive types to be specified with minimal additional syntax.
Datatype-generic programming @cite_20 @cite_9 @cite_27 via universes allows defining a single function over an entire class of datatypes at once, saving developers the effort of implementing the operation for datatypes specific to their programs. As Agda's reflection library evolves and the internal representation of datatypes changes, the tool described in this paper requires maintenance work. A future direction would be to work with a universe extended with support for higher inductive types. In such case, the only metaprograms necessary are those that convert to and from the universe. The metaprograms automating the elimination rules do not need to change as long as the universe is kept the same.
@cite_27 @cite_9 @cite_20
2012619465 2132558197 1614164110
We present a closed dependent type theory whose inductive types are given not by a scheme for generative declarations, but by encoding in a universe. Each inductive datatype arises by interpreting its description - a first-class value in a datatype of descriptions. Moreover, the latter itself has a description. Datatype-generic programming thus becomes ordinary programming. We show some of the resulting generic operations and deploy them in particular, useful ways on the datatype of datatype descriptions itself. Simulations in existing systems suggest that this apparently self-supporting setup is achievable without paradox or infinite regress. Much has been said and done about generic programming approaches in strongly-typed functional languages such as Haskell and Agda. Different approaches use different techniques and are better or worse suited for certain uses, depending on design decisions such as generic view, universe size and complexity, etc. We present a simple and intuitive yet powerful approach to generic programming in Agda using indexed functors. We show a universe incorporating fixed points that supports composition, indexing, and isomorphisms, and generalizes a number of previous approaches to generic programming with fixed points. Our indexed functors come with a map operation which obeys the functor laws, and associated recursion morphisms. Albeit expressive, the universe remains simple enough to allow defining standard recursion schemes as well as decidable equality. As for type-indexed datatypes, we show how to compute the type of one-hole contexts and define the generic zipper. In these lecture notes we give an overview of recent research on the relationship and interaction between two novel ideas in (functional) programming: