Zipper data structure for graphical model editor

Question

I'm writing a graphical editor for a "model" (i.e. a collection of boxes and lines with some kind of semantics, such as UML, the details of which don't matter here). So I want to have a data structure representing the model, and a diagram where an edit to the diagram causes a corresponding change in the model. So if, for instance, a model element has some text in an attribute, and I edit the text in the diagram, I want the model element to be updated.

The model will probably be represented as a tree, but I want to have the diagram editor know as little about the model representation as possible. (I'm using the diagrams framework, so associating arbitrary information with a graphical element is easy). There will probably be a "model" class to encode the interface, if I can just figure out what that should be.

If I were doing this in an imperative language it would be straightforward: I'd just have a reference from the graphical element in the diagram back to the model element. In theory I could still do this by building up the model from a massive collection of IORefs, but that would be writing a Java program in Haskell.

Clearly, each graphical element is going to have some kind of cookie associated with it that will enable the model update to happen. One simple answer would be to give each model element a unique identifier and store the model in a Data.Map lookup table. But that requires significant bookkeeping to ensure that no two model elements get the same identifier. It also strikes me as a "stringly typed" solution; you have to handle cases where an object is deleted but there is a dangling reference to it elsewhere, and its difficult to say anything about the internal structure of the model in your types.

On the other hand Oleg's writings about zippers with multiple holes and cursors with clear transactional sharing sounds like a better option, if only I could understand it. I get the basic idea of list and tree zippers and the differentiation of a data structure. Would it be possible for every element in a diagram to hold a cursor into a zipper of the model? So that if a change is made it can then be committed to all the other cursors? Including tree operations (such as moving a subtree from one place to another)?

It would particularly help me at this point if there was some kind of tutorial on delimited continuations, and an explanation of how they make Oleg's multi-cursor zippers work, that is a bit less steep than Oleg's postings?

Finke

Maybe Chung-chieh Shan’s blog? : conway.rutgers.edu/~ccshan/wiki/blog/posts/WalkZip1 . Note, Blobs (wxHaskell) is a library for writing "network editors" - it has probably bit-rotted but it may be less work to update it than start afresh with Diagrams. – Callipygian

Thanks. I've started working through it. I'll let you know if it leads to an answer. – Finke

Answer 1

I think you're currently working from a design in which each node in the model tree is represented by a separate graphical widget, and each of these widgets may update the model independently. If so, I don't believe that a multi-hole zipper will be very practical. The problem is that the complexity of the zipper grows quickly with the number of holes you wish to support. As you get much beyond 2 terms, the size of the zipper will get quite large. From a differentiation point of view, a 2-hole zipper is a zipper over 1-hole zippers, so the complexity grows by operation of the chain rule.

Instead, you can borrow an idea from MVC. Each node is still associated with a widget, but they don't communicate directly. Rather they go through an intermediary controller, which maintains a single zipper. When widgets are updated, they notify the controller, which serializes all updates and modifies the zipper accordingly.

The widgets will still need some sort of identifier to reference model nodes. I've found it's often easiest to use the node's path, e.g. [0] for the root, [1,0] for the root's second child, etc. This has a few advantages. It's easy to determine the node a path refers to, and it's also easy for a zipper to calculate the shortest path from the current location to a given node. For a tree structure, they're also unique up to deletion and reinsertion. Even that isn't usually a problem because, when the controller is notified that nodes should be deleted, it can delete the corresponding widgets and disregard any associated updates. As long as the widget lifetime is tied to each node's lifetime, the path will be sufficiently unique to identify any modifications.

For tree operations, I would probably destroy then recreate graphical widgets.

As an example, I have some code which does this sort of thing. In this model there aren't separate widgets for each node, rather I render everything using diagrams then query the diagram based on the click position to get the path into the data model. It's far from complete, and I haven't looked at it for a while, so it might not build, but the code may give you some ideas.

Froghopper

The thing about Oleg's version of zippers is that it doesn't involve differentiating the data structure, but rather using continuations to capture a partial walk. – Finke

@PaulJohnson - Even with continuations capturing a partial walk, there are still the same number of states to be represented, which is where the complexity comes from. It's managed differently because Oleg uses an explicit ordering between continuations, which means that you have to manage the complexity by making sure the continuations are updated in the proper order. I'm not sure which is simpler in practice, but I expect either approach is non-trivial. – Froghopper