Real-World Problems

We’ll walk through some real-world problems, then introduce a little-known data structure that helps us solve all of them. This concept is often utilized in Haskell and Clojure, but don’t worry if you don’t know these languages. You won’t see any Haskell here.

Decompressing a file

Let’s say you want to decompress a file. In a fairly simple algorithm, you might see a structure like this:

• The first set of bytes is metadata that tells you how the following bytes are encoded, as well as their length.
• Some following stream of bytes is the actual encoded data, up to some stopping point.
• The next set of bytes is again more metadata for a following stream, and so on.

To decompress this file, you would need to:

• Gather the metadata for the chunk of data
• Grab the bytes that correspond to the encoded stream
• Decode the data
• (Repeat for all the chunks)

A fairly simple algorithm, but it’s still kind of annoying to write the boilerplate for this.

Gathering device information

Now, let’s say you’re gathering information about hardware devices attached to a computer system. You probably have a motherboard, which has RAM attached to it, and a CPU, and so forth.

It quickly becomes clear that this information is a kind of tree structure:

• Individual devices can have certain properties associated with them.
• Individual devices can also be nested beneath parent devices.

As an example:

• Motherboard
  • <manufacturer>
  • RAM slot 1
    • <manufacturer>
    • <size>
  • RAM slot 2
    • <manufacturer>
    • <size>
  • CPU 1
    • <manufacturer>
    • <speed>
  • etc.

To collect this system information, you’d have to walk the tree in some fashion and collect the data as you go.

This is slightly more complex than the previous example and the implementation would likely be error-prone, when done from scratch.

Prioritizing data sources

Or, let’s say you have a web server that sources data from a number of different places. The data also gets cached in a local DB, where it will serve as the prioritized source of data until the cache expires, at which point you need to look at remote (or third-party) APIs to renew the cache.

Again, this forms a kind of tree:

• Default to cached data
• If the cache is expired or hasn’t been filled yet:
  • Grab the data from some remote service
  • You may even have another remote service as a fallback (let’s say you’re working with unreliable remote data sources)

Analyzing user behavior

Lastly, think about examining data collected from a user’s interaction with an app. How do you analyze the user’s behavior? You could collect the distinct events and make metrics from them, but those really only give you snapshots of what a user has done in aggregate (how many times did they click a button?).

To see why a user has done something, you need to be able to examine the chain of events that led to that button click or purchase: The chain of cause-and-effect.

What Are the Similarities?

• The first example is a form of digital signal processing. Lots of things fall into this category: Encoded audio samples, compressed binary files, etc.
• The second and third examples are forms of breadcrumbs. We have a larger data structure (maybe a file system tree, or pages on a web site) from which we want to highlight a particular path through the structure.
• The fourth example is a more explicit form of time series. We have some sequential data that indicates a trail of history.

You can actually think of all of these examples as kinds of time series. They may not have a strict concept of time, but they all have a concept of a future path and a past history, as well as an index to demarcate the current location in the series.

Introducing the Huet Zipper

In a general sense, the solution to this problem has been around for decades, but it’s been very ad hoc. Most developers usually just have the underlying data structure and a pointer or cursor index into that structure. But, controlling the structure is typically a very manual process.

In 1997, a French computer scientist named Gérard Huet wrote a functional pearl describing an agnostic solution to this problem. He named it a zipper. The idea is that you take a recursive data structure (an array, a list, a tree, etc.) and define an arbitrary set of rules for walking over that structure and aggregating results. (The name comes from the idea that the form of the data structure will change as you traverse it, much like how a physical zipper sort of “glues” and “unglues” materials together.)

Instead of saying “move my pointer over my array for the next 20 bytes and sum up the results” or “walk over this tree breadth-first until the last node is hit and collect the string descriptions”, you’d simply say “walk into my arbitrary structure’s future until some termination criteria is met and process the results using an aggregation function”.

In code, it might look something like this:

myZipper.walkFuture(Condition.TO_END, aggregateFunc);

Or, because zippers also have a sense of the “past”:

myZipper.walkPast(Condition.TO_BEGINNING, aggregateFunc);

It doesn’t matter whether your underlying structure is an array, or a list, or a tree, or a unicorn widget. They all use the same interface. You could even further abstract this by getting “fully functional”:

myZipper.walk(moveFunc, terminationFunc, aggregateFunc);

This could allow you to move forward or back, or even do trickier things like only aggregating over every third element in the structure.

How Zippers Wrap Other Structures

The underlying implementation of a zipper is dependent upon the structure that it’s wrapping, or possibly even by the way in which you want to define walking mechanisms (do you want to walk a tree depth-first or breadth-first?). The “zipper” concept is really just an abstract interface to provide implementations for.

A partial zipper class that wraps a list might look something like this in C#:

class ZipperArray <T> {
    private List<T> _past;
    private List<T> _future;
    private T _index;
}

The tricky part is in defining the termination conditions for walking (you don’t want to allow walking beyond the end of the structure and some traversal methods have specific requirements). There’s also the tricky issue of breaking up the _past and _future parts of the structure. Each underlying structure needs to be handled differently: A list, for example, needs to reverse the _past list, in order to easily walk backwards over it.

To demonstrate, we’ll see what this might look like over a number line. Let’s say we walk forward two elements:

[1] 2 3 4 5 ...  // _index:  1
                 // _past:   []
                 // _future: [2, 3, 4, 5, ...]

1 [2] 3 4 5 ...  // _index:  2
                 // _past:   [1]
                 // _future: [3, 4, 5, ...]

1 2 [3] 4 5 ...  // _index:  3
                 // _past:   [2, 1]
                 // _future: [4, 5, ...]

We’ve had to progressively push the _index onto the _past, while popping the head of the _future into the _index position.

Walking backwards works the same way, except now you push the _index onto the _future, while popping the head of the _past into the _index position:

1 2 [3] 4 5 ...  // _index:  3
                 // _past:   [2, 1]
                 // _future: [4, 5, ...]

1 [2] 3 4 5 ...  // _index:  2
                 // _past:   [1]
                 // _future: [3, 4, 5, ...]

[1] 2 3 4 5 ...  // _index:  1
                 // _past:   []
                 // _future: [2, 3, 4, 5, ...]

One other nuance of a zipper is that the structure being wrapped doesn’t have to strictly be raw data. It could itself be an accessor for retrieving the raw data, such as our real-world example at the beginning for selecting data providers.

Several Linux packages have been written to handle everyday issues strictly from the perspective of using zippers to solve the problem:

• xmonad – a window manager for providing tiled layouts and handling focus
• ZipperFS – a file system written with zipper traversal mechanisms

Maths and Fun Facts

Zippers are actually a form of a mathematical structure called a comonad. For those familiar with monads, a comonad is dual category to a monad. It’s not the inverse of a monad; it’s more like a set of properties that act on the same kinds of data, but in completely different ways.

Imagine you have a chunk of data. Let’s call it a context. A monad defines a set of properties that can perform operations on that context.

Now, imagine you have a bunch of contexts connected in a stream of some fashion. If a monad acts on a single context, a comonad defines a set of properties for selecting other contexts from the same stream. Comonads don’t act on the contexts directly, but rather are a selection mechanism for grabbing a different context.

And to leave you with a fun fact: There are different variations on zippers besides Huet’s zipper. One example is Kiselyov’s zipper, which specifically targets making updates to the structure underlying the zipper through the use of delimited continuations.