The Zipper acts like a linked-list with a cursor, or "focused element"; it's implemented as a pair of lists in opposite orders; or, equivalently but more symmetric, as triple of (List[A], A, List[A])
Say we have a zipper containing [0, 1, 2, 3, 4, 5], and we're focusing on the 3. In code this will look like:
([2, 1, 0], 3, [4, 5])
Where [a, b, c] denotes a singly-linked list, with O(1) head (returning a) and tail (returning [b, c]). Notice that the first list is in reverse order.
To focus on the next element, we put the currently focused element on the first list, and pull the head off the second list:
([3, 2, 1, 0], 4, [5])
And vice versa to focus on the previous element:
([1, 0], 2, [3, 4, 5])
I like to imagine this as a string of beads, with the focused element held in our fingers and the rest hanging down:
3
/ \
2 4
| |
1 5
|
0
To move the focus forwards and backwards, we move our grip to the next/previous bead.
This works nicely as an immutable datastructure, since the tails of both lists can be shared (i.e. we don't need to copy the whole list, just the wrap/unwrap an element on to the head)
Zippers were first applied to lists, but have since been generalised:
- To trees: focusing on one node, and being able to move the focus up, to the left-child, or to the right child
- To having more than one focus
- To datastructures more generally, by treating them as 'derivatives' (as in calculus)
As an example, the XMonad window manager uses a zipper to keep track of the currently-focused window.
I've also used Zippers for window management, e.g. having a list of Displays, with one of them focused (accepting keyboard input); each Display containing a list of Workspaces, with one of them focused (currently shown); and each Workspace containing a list of Windows, with one of them focused (the active window). Keyboard shortcuts could shift between the previous/next Window, Workspace, or Display.
I encountered this when I tried implementing a Brainfuck interpreter in Haskell. Representing the memory array using a List + index would be way too slow; but a Zipper is perfect!
I don’t understand why wouldn’t you just use a list and an index. You can always access list[index+1] or list[index-1] or list[0] or list[list.length-1].
Firstly, accessing an arbitrary list index is O(N), whilst a Zipper can access its focus in O(1) (shifting the focus is O(1) for both Zippers and list+index)
Secondly, using an index forces us to do bounds checks, keep track of the length (or re-calculate it at O(N) cost), etc. whereas a Zipper is "correct by construction"; i.e. every value of type (List[A], A, List[A]) makes sense as a zipper; whereas many values of type (List[A], Nat) don't make sense as zippers; e.g. ([], 42) doesn't make sense. Our logic also becomes easy for pattern-matching, e.g. in Scala:
myZipper match {
case Zipper(xs, x, y::ys) => Zipper(x::xs, y, ys)
case z => z
}
Also, your example of 'list[index-1]' is more complicated than it first appears. In particular, what is the type of 'index'? If it's an integer, then at least half of the possible values are meaningless (negative numbers); if its a natural (AKA unsigned integer), then it's not closed under subtraction (i.e. we have to worry about underflow)!
Thirdly, Zippers can be unbounded in both directions (i.e. the lists can be "infinite"/co-inductive). For example, they're great for implementing Turing machines, starting with an infinite blank tape in both directions. https://en.wikipedia.org/wiki/Coinduction
Fourthly, Zippers have more sharing. Here's an arbitrary example: say we have a zipper like this:
([c, b, a, ...], elem, [x, y, z, ...])
If we shift right, replace the focused element with 'newElem', then shift right again, we'll get this zipper:
([newElem, elem, c, b, a, ...], y, [z, ...])
Those operations take O(1) time and O(1) memory (and produce O(1) garbage, if we're no longer using the old zipper). In particular, since the tails of the lists ([c, b, a, ...] and [z, ...]) are unchanged, the same pointers will appear in both the old and new zippers; there has been no copying. This is important, since those lists could be arbitrarily long (or infinite!).
In contrast, if we did these operations on a list+index, everything before the replaced element would need to be reallocated; i.e. [..., a, b, c, elem, _] would need to be copied, since _ has changed from 'y, z, ...' to 'newElem, z, ...'. That requires O(N) memory allocation, takes O(N) time to do the copying (and produces O(N) garbage, if we don't want the old zipper).
The benefit is the data sharing between the tails. You can very cheaply get a copy of zipper with the data at (or around) the focused element changed while also keeping the original data unchanged. Admittedly, this is something people in functional programming languages probably care much more about.
This zipper stuff is for immutable data structures.. For us normal folk that just use & abuse array's we don't need zippers. :-). Just kidding. I am dieing to find a use for zippers tho, i'm not a functional programmer.
A list and an index creates the possibility that the index is out of bounds, and then your code probably has to check for that scenario and figure out how to handle it.
Say we have a zipper containing [0, 1, 2, 3, 4, 5], and we're focusing on the 3. In code this will look like:
Where [a, b, c] denotes a singly-linked list, with O(1) head (returning a) and tail (returning [b, c]). Notice that the first list is in reverse order.To focus on the next element, we put the currently focused element on the first list, and pull the head off the second list:
And vice versa to focus on the previous element: I like to imagine this as a string of beads, with the focused element held in our fingers and the rest hanging down: To move the focus forwards and backwards, we move our grip to the next/previous bead.This works nicely as an immutable datastructure, since the tails of both lists can be shared (i.e. we don't need to copy the whole list, just the wrap/unwrap an element on to the head)
Zippers were first applied to lists, but have since been generalised:
- To trees: focusing on one node, and being able to move the focus up, to the left-child, or to the right child
- To having more than one focus
- To datastructures more generally, by treating them as 'derivatives' (as in calculus)
https://en.wikipedia.org/wiki/Zipper_(data_structure)
As an example, the XMonad window manager uses a zipper to keep track of the currently-focused window.
I've also used Zippers for window management, e.g. having a list of Displays, with one of them focused (accepting keyboard input); each Display containing a list of Workspaces, with one of them focused (currently shown); and each Workspace containing a list of Windows, with one of them focused (the active window). Keyboard shortcuts could shift between the previous/next Window, Workspace, or Display.