Clowns to the left of me, jokers to the right (pearl) : dissecting data structures

Tools

Mcbride, Conor; (2008) Clowns to the left of me, jokers to the right (pearl) : dissecting data structures. In: POPL '08 Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages. ACM, New York, NY, pp. 287-295. ISBN 978-1-59593-689-9 (https://doi.org/10.1145/1328438.1328474)

Full text not available in this repository.Request a copy

Abstract

This paper introduces a small but useful generalisation to the 'derivative' operation on datatypes underlying Huet's notion of 'zipper', giving a concrete representation to one-hole contexts in data which is undergoing transformation. This operator, 'dissection', turns a container-like functor into a bifunctor representing a one-hole context in which elements to the left of the hole are distinguished in type from elements to its right. I present dissection here as a generic program, albeit for polynomial functors only. The notion is certainly applicable more widely, but here I prefer to concentrate on its diverse applications. For a start, map-like operations over the functor and fold-like operations over the recursive data structure it induces can be expressed by tail recursion alone. Further, the derivative is readily recovered from the dissection. Indeed, it is the dissection structure which delivers Huet's operations for navigating zippers. The original motivation for dissection was to define 'division', capturing the notion of leftmost hole, canonically distinguishing values with no elements from those with at least one. Division gives rise to an isomorphism corresponding to the remainder theorem in algebra. By way of a larger example, division and dissection are exploited to give a relatively efficient generic algorithm for abstracting all occurrences of one term from another in a first-order syntax. The source code for the paper is available online and compiles with recent extensions to the Glasgow Haskell Compiler.

ORCID iDs

Mcbride, Conor ORCID logoORCID: https://orcid.org/0000-0003-1487-0886;
  • Item type:Book Section
    ID code:34659
    Dates:
    Date
    Event
    2008
    Published
    Subjects:UNSPECIFIED
    Department:Faculty of Science > Computer and Information Sciences
    Depositing user: Pure Administrator
    Date deposited:20 Oct 2011 10:27
    Last modified:28 Nov 2024 08:58
    URI:https://strathprints.strath.ac.uk/id/eprint/34659
CORE (COnnecting REpositories)