More Web Proxy on the site http://driver.im/

research-article

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

Author:

Conor McBrideAuthors Info & Claims

POPL '08: Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 287 - 295

https://doi.org/10.1145/1328438.1328474

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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[7]

Richard Bird and Ross Paterson. de Bruijn notation as a nested datatype. Journal of Functional Programming, 9 (1): 77--92, 1999.

Digital Library

[8]

Janusz Brzozowski. Derivatives of regular expressions. Journal of the ACM, 11 (4): 481--494, 1964.

Digital Library

[9]

Jean-Christophe Filliatre. Backtracking iterators. Technical Report 1428, CNRS-LRI, January 2006.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[14]

Gerard Huet. The Zipper. Journal of Functional Programming, 7 (5): 549--554, 1997.

Digital Library

[15]

Patrik Jansson and Johan Jeuring. PolyP-a polytypic programming language extension. In Proceedings of POPL '97, pages 470--482. ACM, 1997.

Digital Library

[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.

Digital Library

[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.

Digital Library

Cited By

Quennet TDagand P(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
https://dl.acm.org/doi/10.1007/978-981-97-8943-6_2
Lorenzen ALeijen DSwierstra W(2023)FP²: Fully in-Place Functional ProgrammingProceedings of the ACM on Programming Languages10.1145/36078407:ICFP(275-304)Online publication date: 31-Aug-2023
https://dl.acm.org/doi/10.1145/3607840
Darragh PAdams M(2020)Parsing with zippers (functional pearl)Proceedings of the ACM on Programming Languages10.1145/34089904:ICFP(1-28)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3408990
Show More Cited By

Index Terms

Clowns to the left of me, jokers to the right (pearl): dissecting data structures
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Representation of mathematical objects
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Functional languages

Recommendations

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

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, '...
Digraph functors which admit both left and right adjoints

For our purposes, two functors and are said to be adjoint if for any digraphs G and H , there exists a homomorphism of ( G ) to H if and only if there exists a homomorphism of G to ( H ) . We investigate the right adjoints characterised by Pultr (1970). ...
On residuated lattices with left and right internal state
Abstract
In this paper, notions of left- and right-state operators on residuated lattices are introduced and some related properties of such operators are investigated. Filters and normal filters generated by a subset in a state residuated ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

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

General Chair:
George Necula
University of California, Berkeley
,
Program Chair:
Philip Wadler
University of Edinburgh

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

Copyright © 2008 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 January 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

POPL08

Sponsor:

POPL08: The 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

January 7 - 12, 2008

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
1,018
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)2

Reflects downloads up to 16 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Quennet TDagand P(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
https://dl.acm.org/doi/10.1007/978-981-97-8943-6_2
Lorenzen ALeijen DSwierstra W(2023)FP²: Fully in-Place Functional ProgrammingProceedings of the ACM on Programming Languages10.1145/36078407:ICFP(275-304)Online publication date: 31-Aug-2023
https://dl.acm.org/doi/10.1145/3607840
Darragh PAdams M(2020)Parsing with zippers (functional pearl)Proceedings of the ACM on Programming Languages10.1145/34089904:ICFP(1-28)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3408990
Delfino TRibeiro RCamarão CSulzmann M(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
https://dl.acm.org/doi/10.1145/3264637.3264646
Tomé Cortiñas CSwierstra WEisenberg RVazou N(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
https://dl.acm.org/doi/10.1145/3240719.3241787
Bransen JMagalhães JCarette JWillcock J(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
https://dl.acm.org/doi/10.1145/2502488.2502490
Löh AMagalhães JJärvi JMu S(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
https://dl.acm.org/doi/10.1145/2036918.2036920
Yorgey B(2010)Species and functors and types, oh my!ACM SIGPLAN Notices10.1145/2088456.186354245:11(147-158)Online publication date: 30-Sep-2010
https://dl.acm.org/doi/10.1145/2088456.1863542
Bergstrom LRainey MReppy JShaw AFluet M(2010)Lazy tree splittingACM SIGPLAN Notices10.1145/1932681.186355845:9(93-104)Online publication date: 27-Sep-2010
https://dl.acm.org/doi/10.1145/1932681.1863558
Bergstrom LRainey MReppy JShaw AFluet MHudak PWeirich S(2010)Lazy tree splittingProceedings of the 15th ACM SIGPLAN international conference on Functional programming10.1145/1863543.1863558(93-104)Online publication date: 27-Sep-2010
https://dl.acm.org/doi/10.1145/1863543.1863558
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents