Generic Deriving of Generic Traversals

Csongor Kiss, Matthew Pickering, Nicolas Wu

Research output: Contribution to journalArticle (Academic Journal)peer-review

291 Downloads (Pure)

Abstract

Functional programmers have an established tradition of using traversals as a design pattern to work with recursive data structures. The technique is so prolific that a whole host of libraries have been designed to help in the task of automatically providing traversals by analysing the generic structure of data types. More recently, lenses have entered the functional scene and have proved themselves to be a simple and versatile mechanism for working with product types. They make it easy to focus on the salient parts of a data structure in a composable and reusable manner.

This paper uses the combination of lenses and traversals to give rise to a library with unprecedented expressivity and flexibility for querying and modifying complex data structures. Furthermore, since lenses and traversals are based on the generic shape of data, this information is used to generate code that is as efficient as hand-optimised versions. The technique leverages the structure of data to produce generic abstractions that are then eliminated by the standard workhorses of modern functional compilers: inlining and specialisation.
Original languageEnglish
Article number85
Number of pages31
JournalProceedings of the ACM on Programming Languages
Volume2
Issue numberICFP
Early online date30 Jul 2018
DOIs
Publication statusPublished - 23 Sep 2018

Keywords

  • generic programming
  • traversals
  • lenses
  • extensibility

Fingerprint Dive into the research topics of 'Generic Deriving of Generic Traversals'. Together they form a unique fingerprint.

Cite this