拉链喜欢数据结构，多个光标 [英] Zipper like data structure with more than one cursor

问题描述

$ b $

当您想要遍历一个树并保持当前位置时，拉链数据结构非常好，但是如果要跟踪多于一个位置，应该使用什么数据结构？ b

让我举个例子说明一下：

• 
  #haskell频道上有人告诉我， yi编辑器代表
  光标位置。这是非常好的，但如果你想要有两个
  游标怎么办？喜欢，如果你想代表一个选择，你需要知道的开始和
  选择的结尾。
  
• 
  在Minotaur的wikibooks例子中，他们使用拉链代表了Minotaur在迷宫中的位置。如果我想将敌人添加到迷宫中，用拉链代表他们的位置将会有意义。
  
• 
  最后一个是从我的迷你项目实际开始的：所有的开始：作为学习Haskell的一部分，我试图使用cairo和gth2hs可视化一个树结构。这已经很好了，但现在我想选择一个或多个节点，并且能够例如移动他们因为可以有多个选择的节点之一，我不能仅仅使用
  的拉链在教科书中定义。
  

有一个简单的（天真的）解决方案，类似于在早期版本的XMonad中使用的解决方案，它涉及有限的地图，如 here 。

也就是说，例如在我的示例项目的情况下，我会将所选节点存储在索引映射中，并使用索引替换主结构中的表示。但这个解决方案有很多缺点。像上面的链接中所解释的那样，或者说，再次在我的例子中，取消选择所有的节点将需要搜索整个树。

解决方案

Oleg的并发拉链通过分隔延续的工作是主要参考。

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.

解决方案

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

这篇关于拉链喜欢数据结构，多个光标的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！