Export or edit this event...

PSU CS Colloquium: Scrap Your Zippers: A Generic Zipper for Heterogeneous Types

Portland State University FAB, Room 86-09
1900 SW Fourth Avenue
Portland, Oregon 97201, US (map)

Access Notes

Building is at 4th and College. Room 86-01 is in the basement, take the elevator or stairs down to basement and follow the signs.



Scrap Your Zippers: A Generic Zipper for Heterogeneous Types

Michael Adams, Indiana University


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


Michael D. Adams will be completing his Ph.D. in Computer Science at Indiana University this summer. He has a B.S. in Computer Science, a B.S in Computer Engineering and a Minor in Mathematics from the University of Kansas.

His research interests are the implementation and construction of programming languages, compilers and software analysis tools that help programmers more easily implement, reason about, prove correct and improve the performance of their programs. This includes areas such as type systems, static analysis, control-flow analysis, compilers and optimization.

In spring 2007, he worked on the X10 language for an internship at IBM Research. In summer 2007, he worked on the Glasgow Haskell Compiler at Microsoft Research. In 2008-2010 he worked for Cadence Research on the Chez Scheme compiler.

He is an avid swing dancer and cyclist.