Scrap Your Zippers: A Generic Zipper for Heterogeneous Types

Michael D. Adams

Status: Published

Abstract

The zipper type provides the ability to efficiently edit tree-shaped data in a purely functional setting by providing constant time edits at a focal point in an immutable structure. It is used in a number of applications and is widely applicable for manipulating tree-shaped data structures.

The traditional zipper suffers from two major limitations, however. First, it operates only on homogeneous types. That is to say, every node the zipper visits must have the same type. In practice, many tree-shaped types do not satisfy this condition, and thus cannot be handled by the traditional zipper. Second, the traditional zipper involves a significant amount of boilerplate code. A custom implementation must be written for each type the zipper traverses. This is error prone and must be updated whenever the type being traversed changes.

The generic zipper presented in this paper overcomes these limitations. It operates over any type and requires no boilerplate code to be written by the user. The only restriction is that the types traversed must be instances of the Data class from the Scrap your Boilerplate framework.

Keywords

Generic programming, Zippers, Scrap your Boilerplate, Heterogeneous Types

Citation

Michael D. Adams. Scrap your zippers: A generic zipper for heterogeneous types. In WGP ’10: Proceedings of the 2010 ACM SIGPLAN workshop on Generic programming, pages 13–24. ACM, New York, NY, USA, 2010. ISBN 978-1-4503-0251-7. doi: 10.1145/1863495.1863499.

BibTeX Entry

@inproceedings{adams2010zippers,
  author = {Adams, Michael D.},
  title = {Scrap Your Zippers: A Generic Zipper for Heterogeneous Types},
  booktitle = {WGP '10: Proceedings of the 2010 ACM SIGPLAN workshop on Generic programming},
  pages = {13--24},
  year = {2010},
  address = {New York, NY, USA},
  publisher = {ACM},
  isbn = {978-1-4503-0251-7},
  doi = {10.1145/1863495.1863499},
}

Copyright Notice

© ACM, 2010. This is the author’s version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in WGP ’10: Proceedings of the 2010 ACM SIGPLAN workshop on Generic programming, (2010). http://doi.acm.org/10.1145/1863495.1863499.