Strange Loop

Visualizing Persistent Data Structures

Basic persistent data structures like a linked list or sorted binary tree are easy enough to grasp from a single picture, but more complex structures are becoming increasingly important and widely used. Interactive animations can help us develop a deep intuition for how these complicated structures evolve over time, and can serve as a profiling tool to highlight inefficiencies in our data models.

We'll look at some old chestnuts (red-black trees, queues, deques, finger trees) and some modern classics like persistent HAMTs and RRB-Trees. Along the way we'll see that data structures come in many different flavors: partially, fully, or confluently persistent; catenable or not; amortized or not; general performance characteristics; query functionality; update functionality and more. We'll examine the importance of those properties from a variety of use case perspectives.

As we're exploring data structures we'll also consider some ways of navigating through them in purely functional languages, like zippers and lenses, and look at how recursive data structures are defined in lazy and eager languages.

By the end you'll have developed your intuitions about persistent data structures and seen how data visualization techniques can help simplify reasoning about tricky structures and processes.

Dann Toliver

Dann Toliver

Bento Box

Author of Daimio. Makes things at Bento Box. Co-founder of Bento Miso, a non-profit collaborative workspace focused on lowering barriers to entry in the technology world. Likes math.