Zipper like data structure with more than one cursor

Question

The Zipper data structure is great when one wants to traverse a tree and keep the current position, but what data structure one should use if they want to track more then one position?

Let me explain with examples:

• Someone on the #haskell channel has told me that zippers are used in yi editor to represent the cursor position. This is great, but what if you want to have two cursors. Like if you want to represent a selection, you need to know the beginning and the end of the selection.
• In the Minotaur example on wikibooks, they use Zipper to represent Minotaur's position inside the labyrinth. If I wanted to add enemy into the labyrinth, representing their position with a Zipper would make as much sense.
• Last one is actualy from my mini project where it all started: As part of learning Haskell I'm trying to visualize a tree structure using cairo and gth2hs. This has gone well so far but now I would like to select one or more of the nodes and be able to e.g. move them around. Because there can be more then one of the selected nodes I can't just use the Zipper as defined in text books.

There is a trivial (naive?) solution, similar to the one they had used in early versions of XMonad which involves finite maps as explained here.

That is, e.g. in case of my example project, I would store the selected nodes in an indexed map and replace their representation in the main structure with the indices. But this solution has plenty of disadvantages. Like the ones explained in the link above, or say, again in case of my example, unselecting all the nodes would require searching the whole tree.

Road

Answer 1

Oleg's work on "concurrent" zippers via delimited continuations is the main reference.

Spanker

Thank you, that does seem like the answer to my question. It's just a shame that they use all the constructs a newbie fears the most (Monads, Monad Transformers, Continuations, -fglasgow-exts). They even made things harder by adjusting the continuation library. So it's gonna take me a while to grok that. If I may another question, you seem to have been on Haskell scene for a while now, will I ever stop feeling like I'm shooting myself in a foot by learning Haskell :) (in a sense that this would have been so easy to achieve in a OO language)? – Road

@inetic, it depends only on you, it takes dedication in learning but the rewards are worth it. Also, you don't have to fully understand all the higher level concepts they talk about to enjoy programming in Haskell. – Conatus

"Zippers with several holes" is under that Oleg link at okmij.org/ftp/continuations/zipper.html#zipper2 – Rockett

Answer 2

See this paper . I seem to recall reading somewhere that the second derivative has two holes, which is probably what you want.

Laird

McBride's paper's certainly worth reading. Note though that "differentiating" the structure is only half a Huet zipper: you must still define the navigation part. And all of that work is a manual way of replicating what you get for free when using delimited continuations. – Warty

My mind is completely blown! This technique so simple but so awesome!!! Just compute the derivative of f x = f (x^2) twice and get f'' x = 2 * f' (x ^ 2) + (2 * x) ^ 2 * f'' (x ^ 2)), which is a zipper data structure needed for 2 pointers on infinite tree I'd never come up with! – Grecian