F# zipper with pipe forward

By: on December 30, 2010

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.

FacebookTwitterGoogle+

8 Comments

  1. Frank Shearar says:

    Funnily enough, I spent this week playing around with zippers too. You can find my experiments at http://www.squeaksource.com/Zippers.html

    The translation of F# (or OCaml) into Smalltalk wasn’t hard. What caused most difficulty was that I chose to represent a tree with one object, a ZTree, which has both a value and a list of children. Next time I’d probably just use an OrderedCollection (= Section) and objects (= Item). Obviously, that results in an untyped/heterogeneous tree.

    But apart from that, a data structure maps directly into a class definition with one private setter-of-state, one class-side constructor calling that private method, and a bunch of accessor methods. For example, you’d create a tree like so: ZTree value: 1 children: {ZTree value: 2. ZTree value: 3}

    The zipper itself ends up as a class whose navigating/mutating methods all return zippers, and wrapping two pieces of state (the focus, and path). The zipper help function becomes a method on the structure under navigation.

    Smalltalk’s keyword syntax gets in the way a bit of readability for a change. The final tree-changer code of the post becomes this, which has too many parentheses for my liking:

    ((tree zipper down right changeTo: ‘-’) right down changeTo: ‘p’) insertRight: ‘-’) root

    The parentheses are necessary (a) because otherwise you’d be sending a message #changeTo:changeTo:changeTo: and (b) parsing keyword sends is eager, so “tree zipper changeTo: ‘-’ right” really means “send #changeTo: to the object returned by tree zipper, with the value of ‘-’ right as the sole parameter.”

    But hey, I found translating the post into Haskell required more parentheses than I’d expected. (Admittedly that might be because I have almost no experience in Haskell.)

    (Edit: corrected URL)

  2. Frank Shearar says:

    Oh sigh. That link should be http://www.squeaksource.com/Zippers.html

  3. tonyg says:

    @Frank: interesting re keyword syntax. IIRC that was the motivation for Self’s slightly-different take on keywords: Self requires each part of a selector after the first to start with an upper-case letter, so that #changeTo:changeTo:changeTo: would not be a valid selector (it’d have to be #changeTo:ChangeTo:ChangeTo:). It doesn’t help with the issue of (‘-’ right), of course. Isn’t it strange that C++/Java-like syntax does well in this case? tree.zipper.down.right.changeTo(‘-’).right.down.changeTo(‘p’).insertRight(‘-’).root

  4. Frank Shearar says:

    @tonyg Yes, I’d read exactly that the other day in I forget which paper. You could write keyword selectors like that in Smalltalk, but of course that wouldn’t affect the parsing issue.

    What’s really annoying is that the keyword syntax works so well most of the time… except when like here there are long changes of unary messages in between the parts of the keyword selector. The keyword selectors get hard to read when their parts are no longer lexically proximate.

    IIRC Croquet/Open Cobalt extended their Compiler to support positional message sends, so it is possible to write some parts of your API in a C-like fashion. I can hear some folks on squeak-dev saying “well then don’t have such long message chains”. Breaking things up like this doesn’t look much better:

    zipper := tree zipper down right changeTo: ‘-’.
    zipper := zipper right down changeTo: ‘p’.
    zipper := zipper insertRight: ‘-’.
    zipper root

  5. tonyg says:

    Another interesting option would be to permit parentheses for grouping a single message:

    tree zipper down right (changeTo: ‘-’) right down (changeTo: ‘p’) (insertRight: ‘-’) root

    Which is a direction I’m investigating at the moment. It feels right somehow: it makes messages feel more first-class. (Going the whole way and making them values leads to confusion though: say x is bound to some message, then is “z x” a send of message #x to z, or a send of the message held in the variable x to z? It’d be nice to have a solution, because it’d make a language that was both OO and functional (in its similarity to the lambda-calculus), but of the many possible remedies I’ve played with so far, none seem satisfactory…)

Post a comment

Your email address will not be published.

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>