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

Accepted Answer

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.

Making a grid-like data type in haskell

Solution

Problem

Related problems