haskell - 二维 zipper

Question

受到最近关于 Haskell 中二维网格的问题的启发，我想知道是否可以创建一个二维 zipper 来跟踪列表列表中的位置。列表上的一维 zipper 使我们能够真正有效地在大型列表中进行本地移动(常见的示例是文本编辑器)。但假设我们有一个像这样的第二个维度:

grid = 
    [[ 1, 2, 3, 4, 5]
    ,[ 6, 7, 8, 9,10]
    ,[11,12,13,14,15]
    ,[16,17,18,19,20]
    ,[21,22,23,24,25]]

我们能否创建某种 zipper 数据结构，以便不仅可以在网格中左右移动，还可以上下移动？如果是这样，如果我们用无限列表的无限列表替换列表的列表，我们仍然可以获得高效的移动吗？

Answer 1

不太完全，不。 zipper 工作原理的关键方面之一是它们通过用于到达结构的路径来表示结构中的位置，加上沿途创建的额外片段，最终结果是您可以沿着该路径回溯并重建结构，如下所示你去。因此，通过数据结构可用的路径的性质限制了 zipper 。

因为位置是由路径标识的，所以每个不同的路径代表不同的位置，因此具有相同值的多个路径的任何数据结构都不能与 zipper 一起使用 - 例如，考虑循环列表或任何其他具有循环路径的结构。

二维空间中的任意移动并不真正符合上述要求，因此我们可以推断二维 zipper 必然会受到一定的限制。例如，您可能会从原点开始，沿着结构行走一条路径，然后沿着该路径回溯一段距离以到达其他点。这也意味着对于结构中的任何点，都存在只能通过原点到达的其他点。

您可以做的就是在数据结构中构建一些二维距离的概念，这样当您沿着结构向下的路径时，您“下方”的点彼此靠近；这个想法是为了最大限度地减少在 2D 空间中移动短距离所需的平均回溯量。这最终与按距离搜索 2D 空间所需的方法大致相同——最近邻搜索、高效的几何交集等——并且可以使用相同类型的数据结构来完成，即space partitioning创建更高维的搜索树。为 quadtree 实现 zipper ，一个kd-tree ，或类似的结构很简单，就像任何其他树一样。