A zipper is a data structure that provides constant time access for some important class of operations, namely access to the current, next, and previous elements, and insert and delete at the current element.
For those not familiar, the difference between a data structure that provides O(log n) or O(n) for an operation, and one that provides constant time, is that the former take longer and longer as the number of elements in the data structure grow, while the latter takes a fixed amount of time, even as the data in the data structure grows.
A zipper uses two lists:
{ [ previous | list of previous items in backwards order ], [ current | list of next items in forward order ] }
So a zipper of the alphabet, that is currently at the letter L looks like:
{ [ K | J,I,H,G,F,E,D,C,B,A ], [ L | M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z ] }
To traverse to the next letter, M, we simply take the head (L) off the second list and append it to the first. That happens in constant time of course.
{ [ L | K,J,I,H,G,F,E,D,C,B,A ], [ M | N,O,P,Q,R,S,T,U,V,W,X,Y,Z ] }
To traverse to the previous letter, we simply take the head (L) off the first list and append it to the second. It’s the same operation, so of course it happens in constant time too.
{ [ K | J,I,H,G,F,E,D,C,B,A ], [ L | M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z ] }
Now let us suppose the IAA (International Alphabet Association) decreed that there should be a new letter ∀ (pronounced vlork) that comes between K and L. We simply insert vlork as the head of the 2nd list. A constant time operation.
{ [ K | J,I,H,G,F,E,D,C,B,A ], [ ∀ | L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z ] }
And when the IAA comes to their senses after the inevitable public outcry, we delete vlork by removing it from the head of the 2nd list. You guessed it, still in constant time.
{ [ K | J,I,H,G,F,E,D,C,B,A ], [ L | M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z ] }
Our example alphabet list has just 26 items. But it could have 26 million items and the time it takes to get the current item, traverse to the next item, traverse to the previous item, insert at the current place, or delete at the current place is constant.
A zipper may not seem like much for languages with pointers or dynamic object references, since it has the same access time characteristics as a doubly-linked list. But for functional languages like Erlang or Haskell, with single assignment and no pointers (very important characteristics for robust concurrency), the zipper is an important data structure.
Thus far, I’ve only talked about zippers and lists. More later on zippers and trees.
References:
Yet Another Article on Zippers, in Erlang
You could have invented zippers
programming
data structures
Erlang
