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?

Drumfish

Answer 1

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.

Tical

"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". Why is having a unique path a key requirement for zippers? I would have thought that any way to represent a "location" in a data structure would suffice – Inbreed

@AnupamJain: Because the fragments used to rebuild are pieces of the original, immutable structure, if one of those contains another path to the "same" location, when you reassemble it that path will still have the original value. The only way to handle it is to walk down both paths and do both replacements--i.e., considering both paths together as the "unique" path. – Tical

@AnupamJain: The more redundant paths possible, the more inefficiency you create. The worst case scenario is something like a cyclic list, where there are an infinite number of paths and each path contains the entire structure, which forces you to rebuild everything. – Tical

Hmm what do you think of my answer below? I'm not sure if it qualifies as a zipper – Inbreed

Thank you very much! I tried various implementations like Anupam's below, and couldn't quite put my finger on why I couldn't get that constant time mutation per movement. This explains the core of the issue perfectly – Drumfish

@habitue: If you're still interested in exploring the idea, I note the spacepart package seems to be abandoned. A more extensive space partitioning library with distance-aware zippers would be a nice addition to hackage... – Tical

Answer 2

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

Inbreed

This provides the same operations as a Zipper, but it isn't one. A zipper, as introduced by Huet, has a constant amount of allocation per navigation step. Your implementation has allocation costs which depend on the size of the total data structure. So, this might be a useful data structure for your use case, I don't know. But I wouldn't call it a zipper. – Tomi

Ah that makes sense.. I don't know what I was thinking – Inbreed

@jmg: To be fair, this is a zipper--specifically, two standard list zippers nested, operating on nested lists. The actual navigation steps are moving along an inner list, or moving along the outer list when the selection is the first element of an inner list. The issue is that "up" and "down" aren't part of this zipper's navigation. – Tical

@C.A.McCann: You could say that, but in the end you don't have the usual benefits of a zipper. Above, I already said that it might be useful data structure, depending on the circumstances. I just wouldn't call it a zipper. But, yes it is like to zippers with a reduced set of navigation primitives. – Tomi

Answer 3

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://mcmap.net/q/588751/-birecursively-defining-a-doubly-infinite-list-of-lists
  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.

Bally

Wait. It's not really O(1), is it? It allocates O(MN) in M+N operations, so we could say O(N), ✓N for average use, right? I need to sleep over it. (My use case is O(MN) space for MN operations, which is constant enough.) – Bally