8 Functional data structures

This chapter motivates functional data structures as a practical way to write programs without mutation, even eliminating a central mutable “owner” when ordering of updates is hard or error-prone. It introduces persistent, shareable structures that make creating modified versions efficient rather than relying on full copies. The chapter frames the trade-offs and goals: immutability by design, structural sharing for performance, and behavior comparable to conventional containers, culminating in a comparison between standard vector usage and its immutable counterpart.

It begins with immutable singly linked lists as the canonical example of structural sharing. Prepending and removing from the front run in constant time by reusing existing nodes, while appending, middle insertions, and removals require copying the prefix and are linear. Because nodes are shared by multiple lists, memory must be managed with reference counting (for example, shared ownership) and with a non-recursive destruction strategy to avoid stack overflows; thread safety requires care beyond basic reference counting. The result is a list well-suited for stack-like workloads, but not for random access or frequent tail/middle updates.

The chapter’s main workhorse is the bitmapped vector trie (a persistent vector). With a fixed branching factor that’s a power of two (typically 32), it forms a shallow tree of fixed-size chunks, delivering fast, effectively constant-time indexed lookup. Updates, appends, and pops are implemented by copying only the nodes along the path from the root to the affected leaf, sharing all untouched structure; these operations are effectively O(1). Prepending, mid-inserts, and concatenation remain linear, mirroring standard vectors. Although indirection and chunked storage slightly reduce cache friendliness versus std::vector, the persistent vector excels at rapid copying and safe sharing of versions—exactly what immutable functional code needs.

A singly linked list. Each node contains a value and a pointer to the next item.

Prepending an element to an immutable list returns a new list. It doesn’t need to copy any of the existing nodes from the original list; it can reuse them. This approach isn’t viable in the mutable version of the list because changing one list would have the side effect of changing all other lists that share data with it.

Getting the tail of a list creates a new list from the original one that will contain the same elements modulo the head. The resulting list can share all the nodes with the original one, and still nothing needs to be copied.

If you tried the same trick of avoiding copying the data when appending to a list, and made the last element in the old list point to the newly created node, you’d change every list that shared its data with the list you were modifying. It’s interesting to note that if two lists share any nodes, they share the end as well.

If you want to create a list that’s the same as the original but has an extra element at its end, you need to copy all nodes from the original list and only then point the last node to the newly created node that contains the appended value.

Inserting an element into the middle of a list is equivalent to removing all the items from the original list that should come before the element you’re inserting and then prepending that element and all the previously removed items. The only nodes you share with the original list are nodes that come after the item you’ve inserted.

When a list is deleted, you need to destroy the nodes that no other list uses. The nodes don’t know how many lists they belong to, but they need to know how many immediate parents they have. When all parents of a node are destroyed, you can destroy that node as well; there’s no list that it’s the head of, or any node that points to it.

If you have at most m elements, the bitmapped vector trie will contain just one COW vector.

When you add an item that can’t fit into a vector of capacity m, you create another vector and place the new element inside it. To track all the vectors you create, you need an index: a new vector of capacity m that holds the pointer to the vectors you created to hold the data. You get a trie with two levels.

When you fill up the root vector and can’t add more items to it, you create another trie in which you can store more elements. To keep track of all these tries, you create a new root node.

Finding the item for a given index is easy. Each level has internal indices going from 0 to m, and m should be a power of 2 (in this figure, m = 4, although in reality it’s usually 32). The internal indices of each node, if looked at as arrays of bits, go from 00 to 11. You can look at the index of the requested element as an array of bits that you split into two-by-two chunks. Each chunk is the internal index in the corresponding trie node.

In a mutable binary vector trie, appending a new element is simple. If an empty space is left in the last leaf node, you can store the value there. If all leaves are full, you create a new one. You need to create a pointer to the new leaf in the level above it. Recursively, if the parent node has room, you store the pointer there. If not, you create a new node, and you store a pointer to it in the level above it. This is repeated until you reach the root. If the root node has no room, you create a new node and make it a parent of the previous one.

In the immutable binary vector trie, the principle of adding a new element is the same. The difference is that, because you want the previous collection to be untouched, you need to create a new trie to hold the new data. Fortunately, as was the case with linked lists, you can share most of the data between the old and the new tries. The only nodes you need to create are those on the path to the element you’re adding. All other nodes can be shared.

When appending a new element to a trie that has a leaf with room for it, you have to duplicate that leaf and all its parents. You can then add the new value into the newly copied leaf.

When you don’t have any room in the last leaf, you need to create a new one that contains just the element you’re appending to the trie. The newly created leaf should be inserted into the layer above it.

This is a corner case where none of the leaves have space, and none of the other nodes, including the root, have space. In this case, you can’t create a new path inside this trie, so you need to create a new root item that will link to the previous trie, and a new trie with the same depth that contains just the newly added item.

• The main optimization in all immutable data structures, which are also called persistent, is data sharing. It allows you to keep many slightly modified versions of the same data without the memory overhead you’d have if you used the classes from the standard library.
• Having an efficient way to store past values of a variable allows you to travel through the history of your program. If you store all the previous states of your program, you can jump back to any of them whenever you want.
• Similar modifications exist for other structures as well. For example, if you needed an immutable associative container, you could use red-black trees, modified to share the data between different instances, similar to what you did for the bitmapped vector trie.
• Immutable data structures have always been an active area of research. Many contributions came from academia (as is often the case with functional programming), as well as from developers.
• It’s always worth checking which structures would be suited best for any particular case. Unlike the go-to collection in C++ (std::vector), all immutable data structures have downsides (even if they’re as magical as bitmapped vector tries). Some of them might not be well suited for a given case.

FAQ