Ask HN: What are some cool but obscure data structures you know about?
The Zipper acts like a linked-list with a cursor, or &quot;focused element&quot;; it&#x27;s implemented as a pair of lists in opposite orders; or, equivalently but more symmetric, as triple of (List[A], A, List[A])<p>Say we have a zipper containing [0, 1, 2, 3, 4, 5], and we&#x27;re focusing on the 3. In code this will look like:<p><pre><code>    ([2, 1, 0], 3, [4, 5])
</code></pre>
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.<p>To focus on the next element, we put the currently focused element on the first list, and pull the head off the second list:<p><pre><code>    ([3, 2, 1, 0], 4, [5])
</code></pre>
And vice versa to focus on the previous element:<p><pre><code>    ([1, 0], 2, [3, 4, 5])
</code></pre>
I like to imagine this as a string of beads, with the focused element held in our fingers and the rest hanging down:<p><pre><code>     3
    &#x2F; \
    2 4
    | |
    1 5
    |
    0
</code></pre>
To move the focus forwards and backwards, we move our grip to the next&#x2F;previous bead.<p>This works nicely as an immutable datastructure, since the tails of both lists can be shared (i.e. we don&#x27;t need to copy the whole list, just the wrap&#x2F;unwrap an element on to the head)<p>Zippers were first applied to lists, but have since been generalised:<p>- To trees: focusing on one node, and being able to move the focus up, to the left-child, or to the right child<p>- To having more than one focus<p>- To datastructures more generally, by treating them as &#x27;derivatives&#x27; (as in calculus)<p><a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Zipper_(data_structure)" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Zipper_(data_structure)</a><p>As an example, the XMonad window manager uses a zipper to keep track of the currently-focused window.<p>I&#x27;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&#x2F;next Window, Workspace, or Display.