二维拉链 [英] Two-dimensional zipper

问题描述

由于最近关于Haskell的2d网格问题的启发，我想知道是否可以创建一个二维拉链来跟踪列表中的位置。列表中的一维拉链允许我们在一个大的列表（通常的例子是文本编辑器）中真正有效地移动本地。但是让我们说我们有这样的第二个维度：

  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]] 
  

我们可以创建某种拉链的数据结构，不仅可以在网格中左右上下移动，还可上下​​移动？如果是这样，如果我们用无限列表的无限列表替换列表，我们还能得到有效的移动吗？

解决方案

不相当，不。拉链如何工作的关键方面之一是它们通过用于达到它的路径代表结构中的位置，以及沿途创建的额外碎片，最终结果是您可以沿着该路径回溯并重建结构你走。通过数据结构可用的路径的性质因此限制了拉链。

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

任意运动2D空间并不符合上述要求，因此我们可以推断出2D拉链一定会受到限制。也许你从起点开始，走过一条通过结构的路径，然后沿一条路径回溯一些距离，以达到其他点。这也意味着对于结构中的任何一点，还有其他一些点只能通过原点来达到。

你可以做什么将二维距离的一些概念构建到数据结构中，这样当您沿着结构中的路径向下时，下面的点彼此接近;这个想法是最小化在2D空间中移动短距离平均需要的回溯量。这最终是通过距离 - 最近邻搜索，高效几何交集，这种事情 - 可以用相同类型的数据结构来搜索2D空间所需的大致相同的方法，即空间分区来创建更高维的搜索树。为四叉树实施拉链，一个 kd-tree 或类似的结构很简单，就像任何其他树一样。

Inspired by the recent question about 2d grids in Haskell, I'm wondering if it would be possible to create a two-dimensional zipper to keep track of a position in a list of lists. A one-dimensional zipper on a list allows us to really efficiently move locally in a large list (the common example being a text editor). But lets say we have a second dimension like this:

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]]

Can we create some kind of zipper data structure to efficiently move not only left and right but up and down in the grid here? If so, what if we replace the list of lists with an infinite list of infinite lists, can we still get efficient movement?

解决方案

Not quite, no. One of the key aspects of how zippers work is that they represent a location in a structure by a path used to reach it, plus extra fragments created along the way, with the end result that you can backtrack along that path and rebuild the structure as you go. The nature of the paths available through the data structure thus constrains the zipper.

Because locations are identified by paths, each distinct path represents a different location, so any data structure with multiple paths to the same value can't be used with a zipper--for example, consider a cyclic list, or any other structure with looping paths.

Arbitrary movement in 2D space doesn't really fit the above requirements, so we can deduce that a 2D zipper would necessarily be somewhat limited. Perhaps you'd start from the origin, walk a path through the structure, and then backtrack along that path some distance in order to reach other points, for example. This also implies that for any point in the structure, there are other points that can only be reached via the origin.

What you can do is build some notion of 2D distance into the data structure, so that as you follow a path down through the structure, the points "below" you are close to each other; the idea is to minimize the amount of backtracking needed on average to move a short distance in 2D space. This ends up being roughly the same approach needed to search 2D space by distance--nearest neighbor searches, efficient geometric intersection, that sort of thing--and can be done with the same kind of data structure, namely space partitioning to create a higher-dimensional search tree. Implementing a zipper for a quadtree, a kd-tree, or similar structures is straightforward, just like any other tree.

这篇关于二维拉链的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！