二维拉链

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空间所需的方法大致相同- 最近邻搜索,有效几何交叉,这种事情 - 并且可以使用相同类型的数据结构完成,即空间分区以创建更高 - 维搜索树.实现四叉树,kd树或类似结构的拉链很简单,就像任何其他树一样.

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