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

maybe you use

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

Answer 2

There are two approaches that I know of:

Collect multiple parameters in some sort of object that is convenient to pass around. Example:

; world is a nested hash, the rest are keys
(defstruct location :world :country :city :building)
(defstruct attribute :object :property)

(defn do-update[location attribute value]
  (let [{:keys [world country city building]} location
        {:keys [object property]} attribute ]
    (update-in world [country city building object property] value)))

This brings you down to two parameters that the caller needs to care about (location and attribute), which may be fair enough if those parameters do not change very often.

The other alternative is a with-X macro, which sets variables for use by the code body:

(defmacro with-location [location & body] ; run body in location context
  (concat
    (list 'let ['{:keys [world country city building] :as location} `~location])
    `(~@body)))

Example use:
(with-location location (println city))

Then whatever the body does, it does to the world/country/city/building set for it, and it can pass the entire thing off to another function using the "pre-assembled" location parameter.

Update: Now with a with-location macro that actually works.

Answer 3

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.