Making a grid-like data type in haskell

Question

Problem

I've been wondering how this could be done efficiently for a while, but for some reason I have been unable to do it. I need to model a rectangular grid, where each field contains some data.

I need to access it via a zipper, where my focus is a field (the value so to speak). The zipper should support the actions goDown, goUp, goLeft and goRight, each changing the focus to the field in the indicated direction, as well as here, which should return the value of the field currently under focus.

While this can be done with a Map, it is inefficient in the sense that changing focus would take log n time, n being the number of elements in the Map, since a Map has logarithmic lookup time.

I need the indicated actions to work in O(1) time.

Example

For illustrative purpose look at the matrix below. The parenthesized number is the current focus.

1 (2) 3
4  5  6
7  8  9

If I applied goRight, I should get:

1  2 (3)
4  5  6
7  8  9

If I applied here now, the value returned should be 3.

Question

How would a data type on the form explained above look in haskell? Is it achievable as a algebraic data type?

Remember that the change of focus, in all four directions, should be doable in O(1) time, as well as reading the value currently in focus.

Cobaltite

Do you need access in O(1) time as well? – Pacifier

Only the indicated actions needs an O(1) execution time. I don't need O(1) lookup, if that is what you mean. – Cobaltite

By access I mean getting and/or replacing the current value in brackets. Still no? – Pacifier

A similar question was asked before. – Fluting

@Pacifier I need to be able to access the current focus in O(1) time. I have just updated the question. – Cobaltite

Reading the value in my answer is O(1), but writing is O(sqrt(n)). I quite like the answer in the linked question though. – Pacifier

@phg -> The accepted answer in the link is acceptable here as well. I guess my question is duplicate then. – Cobaltite

This is a great question. A 2D Zipper could be just fine however perhaps we can achieve even a better Grid type structure composed well enough to suit your particular need. Here is a trial case with it's own problems and possible solutions. – Cards

Answer 1

Ok, I'm disappointed that no one else has given the "right" answer to this problem yet, because I know it's exists but I will not be able to explain it well. My answer is bases on http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html

First off, a standard, that is 1d zipper could be:

Data U x = U [x] x [x]

the first element is a reversed list of all elements "left" the focus, then the focus element then a list of all elements "right" the focus. E.g.:

U [-1,-2,-3] 0 [1,2,3]

We can then move the zipper left and right. You have to decide what to do when we run off the edge of the grid. The original post simply postulated an infinite grid so that corner case is left as an exercise to the reader.

left  (U (a:as) x zs) = U as a (x:zs)
right (U as x (z:zs)) = U (x:as) z zs

Now everything that looks like a container should be a Functor so:

instance Functor U where
  fmap f (U a x z) = U (map f a) (f x) (map f z)

At this point is really where I wish someone else woudl jump in to explain what I'm about to do and why. I'm going to make U an instance of Control.Comonad. The best I can explain is that comonads are kind of inside-out monads. Instead of giving you one element and asking you to create a container with a new value (>>= :: Monad m => m a -> (a -> m b) -> m b), Comonads give you the whole structure and only ask for the value that belongs at the focus: (=>>) :: Comonad w=>w a -> (w a -> b) -> w

So using the terms of Control.Comonad in the comonad-3.0.2 package:

Instance Comonad U where
  -- extract :: U a -> a   -- called coreturn in the post
  extract (U _ x _) = x

  -- duplicate :: U a -> U (U a)  -- called cojoin in the post
  duplicate x = U (tail $ iterate left x) x (tail $ iterate right x)

duplicate gives you a Zipper of Zippers with each one shifted left or right by one more element then the last. It seems like a huge amount of memory but Haskell is lazy and the actual memory footprint is very small and on the order of O(n) for the full set and O(1) if you don't look around at all.

But this is all in just one dimension. Again for reasons I'm not smart enough to explain extending this to two dimensions id dead easy:

data U2 x = U2 (U(U x))

instance Functor U2 where
  fmap f (U2 y) = U2 $ fmap (fmap f) y

instance Comonad U2 where
  extract (U2 y) = extract (extract y)
  duplicate (U2 y) = fmap U2 $ U2 $ roll $ role y where
    iterate' f = tail . iterate f
    role x = U (iterate' (fmap left) x) x (iterate' (fmap right) x)

The duplicate function now creates a grid of grids, each appropriately shifted. So

goLeft  u = let (U _ (U x _ _) _) = duplicate u in x
goRight u = let (U _ (U _ _ x) _) = duplicate u in x
goUp      = left  . duplicate
goDown    = right . duplicate
here      = extract

Because Haskell is lazy all these are O(1) functions. Even more interesting you can change here for O(1) cost in both time and memory and use neighborhood cells in the calculation. This make implimenting something like a game of life cellular automata as easy as

rule  (U2 (U
      (U (u0:_) u1 (u2:_):_)
      (U (u3:_) u4 (u5:_))
      (U (u6:_) u7 (u8:_):_))) =
         let n = length $ filter id [u0,u1,u2,u3,u5,u6,u7,u8] in
           u4 && (n==2 || n==3) || (not u4) && n==3

-- assume u is the original graph each step is
step u = u =>> rule

In addation to the blog post above, I suggest searching Google for Comonad to find out more, particularly as I am not the best at explaining this stuff.

Brebner

Answer 2

This might not be what you're asking, but I'd like to hear why first to suggest a better answer.

data GridWithZipper a = GridWithZipper { grid :: [[a]]
                                       , gwzx :: Int
                                       , gwzy :: Int
                                       }

goLeft  gwz = gwz { gwzx = gwzx gwz - 1 }
goRight gwz = gwz { gwzx = gwzx gwz + 1 }
goUp    gwz = gwz { gwzy = gwzy gwz - 1 }
goDown  gwz = gwz { gwzy = gwzx gwz + 1 }

get gwz = grid gwz !! gwzx gwz !! gwzy gwz

All the operations are obviously O(1).

All the go operations are O(1), getting and setting are O(sqrt(n)), however.

Pacifier

Well, the point of a zipper be able to access the value under focus in O(1) time. Updating my question... – Cobaltite

The !! operation on list is not O(1), it's O(n). Switching from a list to Vector should solve the issue however. – Conquistador

@NikitaVolkov Even with Vector this can't update the focused value in O(1). – Overtone