Abstract
Inductive families provide a convenient way of programming with dependent types. Yet, when it comes to compilation, their default linked-tree runtime representations, as well as the need to convert between different indexed views of the same data, can lead to unsatisfactory runtime performance. In this paper, we introduce a language with dependent types, and inductive families with customisable representations. Representations are a version of Wadler’s views, refined to inductive families like in Epigram, but with compilation guarantees: a represented inductive family will not leave any runtime traces behind, without relying on heuristics such as deforestation. This way, we can build a library of convenient inductive families based on a minimal set of primitives, whose re-indexing and conversion functions are erased during compilation. We show how we can express optimisation techniques such as representing -like types as GMP-style big integers, without special casing in the compiler. With dependent types, reasoning about data representations is also possible through a provided modality. This yields computationally irrelevant isomorphisms between the original and represented data.
| Original language | English |
|---|---|
| Title of host publication | Trends in functional programming |
| Subtitle of host publication | 26th international symposium, TFP 2025, Oxford, UK, January 14–16, 2025 revised selected papers |
| Editors | Jeremy Gibbons |
| Place of Publication | Cham |
| Publisher | Springer Nature |
| Pages | 302-328 |
| Number of pages | 27 |
| ISBN (Electronic) | 9783031997518 |
| ISBN (Print) | 9783031997501 |
| DOIs | |
| Publication status | Published - 1 Oct 2025 |
| Event | 26th International Symposium on Trends in Functional Programming - University of Oxford, Oxford, United Kingdom Duration: 13 Jan 2025 → 16 Jan 2025 https://trendsfp.github.io/2025/ |
Publication series
| Name | Lectures notes in computer science |
|---|---|
| Volume | 15652 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 26th International Symposium on Trends in Functional Programming |
|---|---|
| Abbreviated title | TFP 2025 |
| Country/Territory | United Kingdom |
| City | Oxford |
| Period | 13/01/25 → 16/01/25 |
| Internet address |
Keywords
- Dependent types
- Memory representation
- Inductive families
Fingerprint
Dive into the research topics of 'Custom representations of inductive families'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver