Managing updates to nested immutable data structures in functional languages

Question

I've noticed while on my quest to lean functional programming that there are cases when parameter lists start to become excessive when using nested immutable data structures. This is because when making an update to an object state, you need to update all the parent nodes in the data structure as well. Note that here I take "update" to mean "return a new immutable object with the appropriate change".

e.g. the kind of function I have found myself writing (Clojure example) is:

(defn update-object-in-world [world country city building object property value]
  (update-country-in-world world
    (update-city-in-country country
      (update-building-in-city building
        (update-object-in-building object property value))))) 

All this to update one simple property is pretty ugly, but in addition the caller has to assemble all the parameters!

This must be a fairly common requirement when dealing with immutable data structures in functional languages generally, so is there a good pattern or trick to avoid this that I should be using instead?

Answer 1

Try

(update-in 
  world 
  [country city building] 
  (update-object-in-building object property value))

Answer 2

A classic general-purpose solution to this problem is what's called a "zipper" data structure. There are a number of variations, but the basic idea is simple: Given a nested data structure, take it apart as you traverse it, so that at each step you have a "current" element and a list of fragments representing how to reconstruct the rest of the data structure "above" the current element. A zipper can perhaps be thought of as a "cursor" that can move through an immutable data structure, replacing pieces as it goes, recreating only the parts it has to.

In the trivial case of a list, the fragments are just the previous elements of the list, stored in reverse order, and traversal is just moving the first element of one list to the other.

In the nontrivial but still simple case of a binary tree, the fragments each consist of a value and a subtree, identified as either right or left. Moving the zipper "down-left" involves adding to the fragment list the current element's value and right child, making the left child the new current element. Moving "down-right" works similarly, and moving "up" is done by combining the current element with the first value and subtree on the fragment list.

While the basic idea of the zipper is very general, constructing a zipper for a specific data structure usually requires some specialized bits, such as custom traversal or construction operations, to be used by a generic zipper implementation.

The original paper describing zippers (warning, PDF) gives example code in OCaml for an implementation storing fragments with an explicit path through a tree. Unsurprisingly, plenty of material can also be found on zippers in Haskell. As an alternative to constructing an explicit path and fragment list, zippers can be implemented in Scheme using continuations. And finally, there seems to even be a tree-oriented zipper provided by Clojure.