受最近关于 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]]
我们可以创建某种拉链数据结构来有效地在网格中左右移动而且上下移动吗？如果是这样，如果我们用无限列表的无限列表替换列表列表，我们还能获得有效的移动吗？
不完全，不。拉链如何工作的一个关键方面是，它们通过用于到达它的路径表示结构中的位置，以及沿途创建的额外片段，最终结果是您可以沿着该路径回溯并重建结构你去。因此，通过数据结构可用的路径的性质限制了拉链。
因为位置是由路径标识的，每条不同的路径代表一个不同的位置，所以任何具有相同值的多个路径的数据结构都不能与拉链一起使用——例如，考虑一个循环列表，或任何其他具有循环的结构路径。
2D 空间中的任意移动并不真正符合上述要求，因此我们可以推断出 2D 拉链必然会受到一定的限制。例如，也许您会从原点开始，穿过结构，然后沿着该路径回溯一段距离以到达其他点。这也意味着对于结构中的任何点，都有其他点只能通过原点到达。
您可以做的是在数据结构中构建一些 2D 距离的概念，这样当您沿着结构向下走时，“下方”的点彼此靠近；这个想法是最小化在 2D 空间中移动短距离所需的平均回溯量。这最终与按距离搜索 2D 空间所需的方法大致相同——最近邻搜索、有效的几何交集等等——并且可以使用相同类型的数据结构来完成，即空间分区以创建更高的维搜索树。为quadtree、kd-tree或类似结构实现 zipper很简单，就像任何其他树一样。
那么你可以使用一些简单的东西，比如下面的代码。我们用所选元素的顶行、所选元素的底行、所选元素左侧的元素和所选元素右侧的元素来表示一个表格。
顶部行和左侧元素以相反的顺序存储，以实现高效移动。
我不确定这是否符合拉链的条件，因为即使我们在数据结构中拥有一个“位置”，它也不是一个“路径”。
-- 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
我一直在寻找类似的东西：一种廉价且轻松地导航（包括“向后”）列表的双重无限列表的方法。这是我的看法。
如果我仔细阅读其他答案，我在这里展示的并不是真正的拉链：虽然导航是摊销 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 <$> 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
数据结构应该是不言自明的。Up and left 可以承受得住严格，因为我们是从单链表构建的。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删除s可能会使该界面更易于使用。自然而然，风险自负。
这可能有点离题，因为它也不是真正的拉链，但它解决了我的问题；由于这是我第一次寻找解决方案时出现的问题，因此我将其发布在这里是为了帮助其他人。