二维拉链

Question

受到最近在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]]

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

Answer 1

不完全是，不。拉链如何工作的一个关键方面是，它们通过用于到达结构的路径来表示结构中的位置，以及在此过程中创建的额外片段，最终结果是您可以沿着该路径回溯并在前进中重建结构。因此，通过数据结构可用的路径的性质限制了拉链。

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

在2D空间中的任意移动并不真正符合上述要求，因此我们可以推断2D拉链一定会有一定的局限性。也许你会从原点开始，走一条穿过结构的路径，然后沿着这条路径回溯一段距离，例如，为了到达其他点。这也意味着对于结构中的任何点，还有其他只能通过原点到达的点。

你可以做的是在数据结构中建立一些2D距离的概念，这样当你沿着结构中的一条路径往下走时，你“下面”的点就会彼此靠近；这个想法是为了最大限度地减少在2D空间中移动短距离所需的平均回溯次数。这最终与通过距离搜索2D空间所需的方法大致相同-最近邻搜索，有效的几何相交，诸如此类的事情-并且可以使用相同的数据结构，即space partitioning来创建更高维度的搜索树。为quadtree、kd-tree或类似结构实现拉链非常简单，就像任何其他树一样。

Answer 2

嗯，你可以使用一些简单的东西，比如下面的代码。我们通过所选元素的顶部行、所选元素的底部行以及所选元素左侧的元素和所选元素右侧的元素来表示表。

顶行和左边的元素以相反的顺序存储，以实现有效的移动。

我不确定这是不是一个拉链，因为即使我们在数据结构中有一个“位置”，它也不是一个“路径”。

-- Table sel left right top bottom
data Table a = Table a [a] [a] [[a]] [[a]] deriving Show

left :: Table a -> Table a
left tab@(Table _ [] _ _ _) = tab
left (Table sel (l:ls) rs ts bs) = Table l ls (sel:rs) ts bs

right :: Table a -> Table a
right tab@(Table _ _ [] _ _) = tab
right (Table sel ls (r:rs) ts bs) = Table r (sel:ls) rs ts bs

up :: Table a -> Table a
up tab@(Table _ _ _ [] _) = tab
up (Table sel ls rs (t:ts) bs) = Table sel' ls' rs' ts (b:bs)
  where
    (ls',(sel':rs')) = splitAt (length ls) t
    b = ls ++ (sel:rs)

down :: Table a -> Table a
down tab@(Table _ _ _ _ []) = tab
down (Table sel ls rs ts (b:bs)) = Table sel' ls' rs' (t:ts) bs
  where
    (ls',(sel':rs')) = splitAt (length ls) b
    t = ls ++ (sel:rs)

tableToList :: Table a -> [[a]]
tableToList (Table sel ls rs ts bs) = (reverse ts) ++ [ls ++ (sel:rs)] ++ bs

listToTable :: [[a]] -> Table a
listToTable [] = error "cannot make empty table"
listToTable ([]:_) = error "cannot make empty table"
listToTable ((t:tr):ts) = Table t [] tr [] ts

这甚至适用于无限列表-

selected :: Table a -> a
selected (Table sel _ _ _ _) = sel

a :: Table Int
a = listToTable $ replicate 10 [1..]

selected a                   #=> 1
selected $ down a            #=> 1
selected $ right $ down a    #=> 2