Two-dimensional zipper

Question

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?

Answer 1

I was looking for something similar: a way to cheaply and easily navigate (which includes going “backwards”) a doubly-infinite list of lists. Here's my take at it.

If I read the others answers carefully, what I'm presenting here isn't really a zipper: while navigation is amortized O(1), the memory used by the zipper structure network is never released. On the other hand, it ought to tie the knot enough for “cells” to be shared no matter the path we take to get to them, which is the kind of topology we'd want on a 2D list of lists.

To compensate, the list of lists used to generate it ought to eventually go unreferenced and garbage-collected.

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

The data structure ought to be self-explanatory. Up and left can afford to be strict because we're building from singly-linked lists. AFAIK, there's no point in maing them lazy in Haskell, as they wouldn't let anything go out of scope anyway.

The lattice is built recursively, expanding the borders of the provided input with Nothing. The lazy-enough variants of zipWith I needed are inspired from answers to another series of questions of mine on the topic.

Here it is in action:

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

The interface can likely be made even easier to use by dropping the Maybes. At your own risk, naturally.

This might be slightly off-topic as it's not a real zipper either, but it solved my problem; and since this is the question that came up when I first looked for a solution, I'm posting it here with the intent it helps someone else.

Answer 2

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.

Answer 3

Well you can use something simple like the following code. We represent a table by the top rows of the selected element, the bottom rows of the selected element, plus the elements to the left of the selected one, and the elements to the right of the selected one.

The top rows and the left elements are stored in a reverse order to enable efficient movement.

I'm not sure if this qualifies as a zipper though, because even though we hold a "location" in the data structure, it is not a "path".

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

This even works for infinite lists -

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