Skip to main navigation Skip to search Skip to main content

Custom representations of inductive families

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 languageEnglish
Title of host publicationTrends in functional programming
Subtitle of host publication26th international symposium, TFP 2025, Oxford, UK, January 14–16, 2025 revised selected papers
EditorsJeremy Gibbons
Place of PublicationCham
PublisherSpringer Nature
Pages302-328
Number of pages27
ISBN (Electronic)9783031997518
ISBN (Print)9783031997501
DOIs
Publication statusPublished - 1 Oct 2025
Event26th 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

NameLectures notes in computer science
Volume15652
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th International Symposium on Trends in Functional Programming
Abbreviated titleTFP 2025
Country/TerritoryUnited Kingdom
CityOxford
Period13/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