24

当一个人想要遍历一棵树并保持当前位置时,Zipper 数据结构很棒,但是如果他们想要跟踪一个以上的位置,应该使用什么数据结构呢?

让我用例子来解释:

  • #haskell 频道上有人告诉我,yi 编辑器中使用拉链来表示光标位置。这很好,但是如果你想有两个游标怎么办。就像如果你想代表一个选择,你需要知道选择的开始和结束。
  • 在 wikibooks 上的 Minotaur 示例中,他们使用 Zipper 来表示 Minotaur 在迷宫中的位置。如果我想将敌人添加到迷宫中,用拉链代表他们的位置同样有意义。
  • 最后一个实际上是从我的迷你项目开始的:作为学习 Haskell 的一部分,我正在尝试使用 cairo 和 gth2hs 可视化树结构。到目前为止一切顺利,但现在我想选择一个或多个节点并能够例如移动它们。因为可以有超过一个选定的节点,所以我不能只使用教科书中定义的 Zipper。

有一个简单的(天真的?)解决方案,类似于他们在 XMonad 的早期版本中使用的解决方案,其中涉及有限映射,如此所述。

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

4

2 回答 2

13

Oleg 关于通过定界延续的“并发”拉链的工作是主要参考资料。

于 2010-08-09T00:00:52.230 回答
10

这篇论文。我似乎记得在某处读过二阶导数有两个孔,这可能是您想要的。

于 2010-08-10T18:52:15.270 回答