当一个人想要遍历一棵树并保持当前位置时,Zipper 数据结构很棒,但是如果他们想要跟踪一个以上的位置,应该使用什么数据结构呢?
让我用例子来解释:
- #haskell 频道上有人告诉我,yi 编辑器中使用拉链来表示光标位置。这很好,但是如果你想有两个游标怎么办。就像如果你想代表一个选择,你需要知道选择的开始和结束。
- 在 wikibooks 上的 Minotaur 示例中,他们使用 Zipper 来表示 Minotaur 在迷宫中的位置。如果我想将敌人添加到迷宫中,用拉链代表他们的位置同样有意义。
- 最后一个实际上是从我的迷你项目开始的:作为学习 Haskell 的一部分,我正在尝试使用 cairo 和 gth2hs 可视化树结构。到目前为止一切顺利,但现在我想选择一个或多个节点并能够例如移动它们。因为可以有超过一个选定的节点,所以我不能只使用教科书中定义的 Zipper。
有一个简单的(天真的?)解决方案,类似于他们在 XMonad 的早期版本中使用的解决方案,其中涉及有限映射,如此处所述。
也就是说,例如在我的示例项目中,我会将选定的节点存储在索引映射中,并用索引替换它们在主结构中的表示。但是这种解决方案有很多缺点。就像上面链接中解释的那样,或者说,在我的示例中,取消选择所有节点将需要搜索整个树。