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

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

11 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationPOPL '08 Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages
Number of pages9
Publication statusPublished - 2008


Dive into the research topics of 'Clowns to the left of me, jokers to the right (pearl): dissecting data structures'. Together they form a unique fingerprint.

Cite this