Zippers: Making Functional "Updates" Efficient (2010)

Summary

In the Haskell stuff, I was planning on moving on to some monad-related stuff. But I had a reader write in, and ask me to write another post on data structures, focusing on a structured called a zipper. A zipper is a remarkably clever idea. It’s not really a single data structure, but rather a way of building data structures in functional languages. The first mention of the structure seems to be a paper by Gerard Huet in 1997, but as he says in the paper, it’s likely that this was used before his paper in functional code — but no one thought to formalize it and write it up. (In the original version of this post, I said the name of the guy who first wrote about zippers was “Carl Huet”. I have absolutely no idea where that came from – I literally had his paper on my lap as I wrote this post, and I still managed to screwed up his name. My apologies!) It also happens that zippers are one of the rare cases of data structures where I think it’s not necessarily clearer to show code. The concept of a zipper is very simple and elegant – but when you see a zippered tree written out as a sequence of type constructors, it’s confusing, rather than clarifying. The basic idea of a zipper is to give you a way of efficiently working with data structures in a functional language. There are a lot of cases where in an imperative language, there’s some basic operation which is cheap and simple in the imperative language, because it’s performed by an in-place update. But in a functional language, you can’t update a field of a data structure: instead, you have to create a new copy of the structure with the altered field. For example, consider the list [a b c d e f g]. Implemented as a cons-list, it’s a list of 7 cons-cells. Suppose you wanted to replace “e” with “q”. In an imperative language, that’s no problem: just do a set-car! of the 5th cell. In a functional language, you would need to create a new list with “q” instead of “e”. You could re-use the common tail [f g], but you would ne...