Zippers

Zippers are a data structure that lets you do fast local updates to a purely functional tree structure. The key property they rely upon is that updates that are nearby can be "buffered" together to minimize copy costs. But instead of buffering operations by actually executing them in batches, they operate by moving a virtual cursor around the structure. Operations at the cursor are cheap, which for many algorithms is sufficient.

We'll talk about the zipper pattern in the abstract, its mathematical foundation given the general theory of algebraic data types, and finally discuss generalizations of the zipper model, including Oleg Kiselyov's delimited-continuation approach to zippers and multi-cursor models.

A full writeup of covered material is available on this site; for more I'd suggest reading Huet's later summary paper (PDF) and Kiselyov's write-up of his approach. More links are in the full material linked to already.