skip to main content
research-article

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

Published: 07 January 2008 Publication History

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.

References

[1]
Michael Abbott, Thorsten Altenkirch, and Neil Ghani. Containers -- constructing strictly positive types. Theoretical Computer Science, 342: 3--27, September 2005a. Applied Semantics: Selected Topics.
[2]
Michael Abbott, Thorsten Altenkirch, Neil Ghani, and Conor McBride. d for data: derivatives of data structures. Fundamenta Informaticae, 65 (1&2): 1--28, 2005b.
[3]
Mads Sig Ager, Dariusz Biernacki, Olivier Danvy, and Jan Midtgaard. A functional correspondence between evaluators and abstract machines. In PPDP, pages 8--19. ACM, 2003.
[4]
William Aitken and John Reppy. Abstract value constructors. Technical Report TR 92-1290, Cornell University, 1992.
[5]
Michael Barr and Charles Wells. Toposes, Triples and Theories, chapter 9. Number 278 in Grundlehren der Mathematischen Wissenschaften. Springer, New York, 1984.
[6]
Richard Bird and Oege de Moor. Algebra of Programming. Prentice Hall, 1997.
[7]
Richard Bird and Ross Paterson. de Bruijn notation as a nested datatype. Journal of Functional Programming, 9 (1): 77--92, 1999.
[8]
Janusz Brzozowski. Derivatives of regular expressions. Journal of the ACM, 11 (4): 481--494, 1964.
[9]
Jean-Christophe Filliatre. Backtracking iterators. Technical Report 1428, CNRS-LRI, January 2006.
[10]
Jeremy Gibbons. Datatype-generic programming. In Roland Backhouse, Jeremy Gibbons, Ralf Hinze, and Johan Jeuring, editors, Spring School on Datatype-Generic Programming, volume 4719 of Lecture Notes in Computer Science. Springer-Verlag, 2007. To appear.
[11]
Thomas Hallgren. Fun with functional dependencies. In Joint Winter Meeting of the Departments of Science and Computer Engineering, Chalmers University of Technology and Goteborg University, Varberg, Sweden., January 2001.
[12]
Ralf Hinze, Johan Jeuring, and Andres Loeh. Type-indexed data types. Science of Computer Programmming, 51: 117--151, 2004.
[13]
Martin Hofmann and Steffen Jost. Static prediction of heap space usage for first-order functional programs. In Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pages 185--197. ACM, 2003.
[14]
Gerard Huet. The Zipper. Journal of Functional Programming, 7 (5): 549--554, 1997.
[15]
Patrik Jansson and Johan Jeuring. PolyP-a polytypic programming language extension. In Proceedings of POPL '97, pages 470--482. ACM, 1997.
[16]
Andre Joyal. Foncteurs analytiques et especes de structures. In Combinatoire enumerative, number 1234 in LNM, pages 126--159. 1986.
[17]
Conor McBride. The Derivative of a Regular Type is its Type of One-Hole Contexts. Available at http://www.cs.nott.ac.uk/~ctm/diff.pdf, 2001.
[18]
Conor McBride. Faking It (Simulating Dependent Types in Haskell). Journal of Functional Programming, 12 (4&5): 375--392, 2002. Special Issue on Haskell.
[19]
Matthias Neubauer, Peter Thiemann, Martin Gasbichler, and Michael Sperber. A Functional Notation for Functional Dependencies. In The 2001 ACM SIGPLAN Haskell Workshop, Firenze, Italy, September 2001.
[20]
Simon Peyton Jones, Mark Jones, and Erik Meijer. Type classes: an exploration of the design space. In Proceedings of the Haskell Workshop, Amsterdam, The Netherlands, June 1997.
[21]
Philip Wadler and Stephen Blott. How to make ad-hoc polymorphism less ad hoc. In 16th ACM Symposium on Principles of Programming Languages, pages 60--76. ACM, January 1989.

Cited By

View all
  • (2024)The Functional Essence of Imperative Binary Search TreesProceedings of the ACM on Programming Languages10.1145/36563988:PLDI(518-542)Online publication date: 20-Jun-2024
  • (2015)Polynomial Functors Constrained by Regular ExpressionsMathematics of Program Construction10.1007/978-3-319-19797-5_6(113-136)Online publication date: 9-Jun-2015
  • (2014)Dynamic Programming for Set Data TypesAdvances in Bioinformatics and Computational Biology10.1007/978-3-319-12418-6_8(57-64)Online publication date: 2014
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices
ACM SIGPLAN Notices  Volume 43, Issue 1
POPL '08
January 2008
420 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1328897
Issue’s Table of Contents
  • cover image ACM Conferences
    POPL '08: Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages
    January 2008
    448 pages
    ISBN:9781595936899
    DOI:10.1145/1328438
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 January 2008
Published in SIGPLAN Volume 43, Issue 1

Check for updates

Author Tags

  1. datatype
  2. differentiation
  3. dissection
  4. division
  5. generic programming
  6. iteration
  7. polynomial
  8. stack
  9. tail recursion
  10. traversal
  11. zipper

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)33
  • Downloads (Last 6 weeks)5
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)The Functional Essence of Imperative Binary Search TreesProceedings of the ACM on Programming Languages10.1145/36563988:PLDI(518-542)Online publication date: 20-Jun-2024
  • (2015)Polynomial Functors Constrained by Regular ExpressionsMathematics of Program Construction10.1007/978-3-319-19797-5_6(113-136)Online publication date: 9-Jun-2015
  • (2014)Dynamic Programming for Set Data TypesAdvances in Bioinformatics and Computational Biology10.1007/978-3-319-12418-6_8(57-64)Online publication date: 2014
  • (2024)Random-Access Lists, from EE to FPProgramming Languages and Systems10.1007/978-981-97-8943-6_2(23-41)Online publication date: 23-Oct-2024
  • (2023)FP²: Fully in-Place Functional ProgrammingProceedings of the ACM on Programming Languages10.1145/36078407:ICFP(275-304)Online publication date: 31-Aug-2023
  • (2020)Parsing with zippers (functional pearl)Proceedings of the ACM on Programming Languages10.1145/34089904:ICFP(1-28)Online publication date: 3-Aug-2020
  • (2018)Towards certified virtual machine-based regular expression parsingProceedings of the XXII Brazilian Symposium on Programming Languages10.1145/3264637.3264646(67-74)Online publication date: 20-Sep-2018
  • (2018)From algebra to abstract machine: a verified generic constructionProceedings of the 3rd ACM SIGPLAN International Workshop on Type-Driven Development10.1145/3240719.3241787(78-90)Online publication date: 27-Sep-2018
  • (2013)Generic representations of tree transformationsProceedings of the 9th ACM SIGPLAN workshop on Generic programming10.1145/2502488.2502490(73-84)Online publication date: 28-Sep-2013
  • (2011)Generic programming with indexed functorsProceedings of the seventh ACM SIGPLAN workshop on Generic programming10.1145/2036918.2036920(1-12)Online publication date: 18-Sep-2011
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media