What is the Zipper data structure and should I be using it?

Let’s start with the Zipper-analog for lists. If you’d like to modify the nth element of a list, it takes O(n) because you have to copy the n-1 first elements. Instead, you can keep the list as a structure ((first n-1 elements reversed) nth element (remaining elements)). For example, the list (1 2 3 4 5 6) modifiable at 3 would be represented as ((2 1) 3 (4 5 6)). Now, you can easily change the 3 to something else. You can also easily move the focus left ((1) 2 (3 4 5 6)) and right ((3 2 1) 4 (5 6)).

A zipper is the same idea applied to trees. You represent a certain focus in the tree plus a context (up to parents, down to children) which gives you the whole tree in a form where it’s easily modifiable at the focus and it’s easy to move the focus up and down.

Leave a Comment