二维拉链

Question

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

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 空间所需的方法大致相同——最近邻搜索、高效的几何交集等——并且可以使用相同类型的数据结构来完成，即空间分区来创建更高维的搜索树。为四叉树实现一个拉链，一个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

Answer 3

我一直在寻找类似的东西：一种廉价且轻松地导航（包括“向后”）双无限列表列表的方法。这是我的看法。

如果我仔细阅读其他答案，我在这里展示的实际上并不是一个拉链：虽然导航的分摊时间为 O(1)，但拉链结构使用的内存 网络从未被释放。另一方面，它应该足以让“单元”能够共享，无论我们采取什么路径到达它们，这就是我们想要的二维列表列表的拓扑类型。

作为补偿，用于生成它的列表列表最终应该不被引用并被垃圾收集。

data FakeZip2D a = Z2 { z2Val   :: a
                      , goUp    :: !( Maybe (FakeZip2D a) )
                      , goDown  ::    Maybe (FakeZip2D a)
                      , goLeft  :: !( Maybe (FakeZip2D a) )
                      , goRight ::    Maybe (FakeZip2D a)
                      }

fromList2 :: [[a]] -> Maybe (FakeZip2D a)
fromList2 xss = head (head zss) where
  extended =       [ repeat Nothing ] ++
    map (\z -> [Nothing] ++ z ++ repeat Nothing) zss ++
                   [ repeat Nothing ]
  zss = zipWith4' row xss extended (drop 1 extended) (drop 2 extended)
  row xs prev cur next = Just <
gt; zipWith5' Z2 xs (tail prev) (tail next)
                                                  cur         (drop 2 cur)

  -- totally inspired by https://stackoverflow.com/a/54096748/12274
  zipWith4' f (a:as) (b:bs) ~(c:cs) ~(d:ds) =
    f a b c d : zipWith4' f as bs cs ds
  zipWith5' f (a:as) (b:bs) ~(c:cs) (d:ds) ~(e:es) =
    f a b c d e : zipWith5' f as bs cs ds es

数据结构应该是不言自明的。向上和向左可以严格，因为我们是从单链表构建的。 AFAIK，在 Haskell 中让他们变得懒惰是没有意义的，因为他们不会让任何东西超出范围。

网格是递归构建的，用 Nothing 扩展所提供输入的边界。我需要的 zipWith 的足够懒的变体的灵感来自我关于该主题的另一系列问题的答案.

实际操作如下：

demo :: IO ()
demo = do
  let multList2 = [[ i*j | j <- [0..] ] | i <- [0..] ]
      multZ2 = fromList2 multList2

  let rows = iterate (>>= goDown) multZ2
      cols = map (iterate (>>= goRight)) rows

  putStrLn "Multiplication table"
  mapM_ (print . map z2Val) $ take 5 $ map (catMaybes . take 5) cols

  putStrLn "List of squares"
  let goDiag = goRight >=> goDown
  print $ map z2Val $ take 25 $ catMaybes $ iterate (>>= goDiag) multZ2

  putStrLn "Convoluted list of squares"
  let goDiag' = goDown >=> goRight >=> goUp >=> goLeft >=> goDiag
  print $ map z2Val $ take 25 $ catMaybes $ iterate (>>= goDiag') multZ2

通过删除“Maybe”，界面可能会变得更加易于使用。当然，风险由您自己承担。

这可能有点偏离主题，因为它也不是真正的拉链，但它解决了我的问题；由于这是我第一次寻找解决方案时出现的问题，因此我将其发布在这里，旨在对其他人有所帮助。