The zipper is a purely functional data structure which is useful when manipulating immutable data structures (see the original paper here by Gerard Huet). Haskell and Clojure both have implementations of the zipper, but I have been unable to find one for use with F#. The original implementation is written in OCAML so is relatively easy to port to F# so this post will briefly walk through the code and give an example of its use.
Here I have defined three types:
- A tree – a simple tree data structure.
- A path – the items in the tuple correspond to everything to the left of a location in the tree, everything above a location in the tree and everything to the right of a location in the tree, and a location in the tree.
- A location- the first item in the tuple is the current location and the second item is the path through the tree to the current location.
The location type is a pointer into the tree structure, by manipulating the location we can traverse the tree.
We use two additional functions to create locations and extract the tree from a location.
We also need functions that will actually manipulate the zipper, these differ from Huet’s OCAML in that the parameters have been swapped so that they can be used with the F#
pipe forward (|>) operator.
Now, we have that we can try it out using FSI:
The pipe forward operator combined with the navigation and modification functions produces a nicely readable line of code that traverses and produces an altered tree. The original tree is also unmodified as this is purely functional code.