[Haskell-cafe] Re: Updating doubly linked lists

[Apfelmus, Heinrich]

S. Günther wrote:
>
>> What kind of structure do you need exactly?
>
> What I really need is a structure which represents a two dimensional 
> grid, i.e. it consists of nodes having a value and a list of
> neighbours attached to it. Point is that if node 1 has node 2 as a
> neighbour then node 2 has to have node 1 as a
> neighbour and each node has the same number of neighbours (currently
> 4, but may vary).

Ah, so you have a rectangular (or later hexagonal?) 2D grid? I suggest
representing it as

  Data.Map (Integer, Integer) a

as explained below.

> That's why I said that thinking about the circular case was just a
> divergence that really got me wondering/interested which is why I posted
> the question in it's short form at the beginning.

Exploring a related easier problem is always a good way to get some
intuition for tackling the harder one. :)

> Anyways, back to the structure I need. One additional thing which will
> happen during the algorithm is that there will be updates to a certain
> local neighboruhood of a node. Now I understand, that that might very
> well be possible with zippers.
>
> Instead of lists of neighbouring nodes I might as well save the paths
> through the graphs separately from the nodes although I only have a very
> vague intuition about how that would look like. And instead of calculating
> a lists of nodes to update, I could calculate a path visting the
> nodes and update them (again beeing unable to escape from the prison
> of an imperative mindset) traversing the path.

A zipper indeed allows you to move to neighbors and update them.

> But the point was that I just had a hard time generalizing what I read
> about zippers to structures where you can have embedded cycles, e.g.
>
> up . left . down . right = id.

If you interpret zippers as the original data structure with a hole,
this is not so difficult. For instance, consider a rectangular grid

  +--+--+--+--+--+--+--+
  |  |  |  |  |  |  |  |
  +--+--+--+--+--+--+--+
  |  |  |  |  |  |  |  |
  +--+--+--+--+--+--+--+
  |  |  |  |  |  |  |  |
  +--+--+--+--+--+--+--+

where you store some data at every node. Now, a zipper is just the old
data structure but one node is marked as "hole"

  +--+--+--+--+--+--+--+
  |  |  |  |  |  |  |  |
  +--+--+--O--+--+--+--+
  |  |  |  |  |  |  |  |
  +--+--+--+--+--+--+--+
  |  |  |  |  |  |  |  |
  +--+--+--+--+--+--+--+

If you represent the grid as a rectangular table

  type Position = (Integer, Integer)
  type Grid a   = Data.Map Position a

a zipper is simply the grid with an extra marker

  type Zipper a = (Grid a, Position)

  left,right,up,down :: Zipper a -> Zipper a
  left  (g,(x,y)) = (g,(x-1,y))
  right (g,(x,y)) = (g,(x+1,y))
  up    (g,(x,y)) = (g,(x,y-1))
  down  (g,(x,y)) = (g,(x,y+1))

  update :: a -> Zipper a -> Zipper a
  update a (g,(x,y)) = (insert (x,y) a g, (x,y))

Note that the  left, right  etc. are not "baked into" the data type but
implemented as normal functions.

In principle, the same could be done for lists

  type ZipperL a = ([a], Int)

  left, right :: ZipperL a -> ZipperL a
  left  (xs,i) = (xs,i-1)
  right (xs,i) = (xs,i+1)

  update :: a -> ZipperL a -> ZipperL a
  update a (xs,i) = (take i xs ++ [a] ++ drop (i+1) xs, i)

This is a valid implementation of a zipper for lists, but of course is
very inefficient,  update  is O(n) . The key thing about the original
list zipper with back and front list is that all operations are O(1).

For the 2D grid zipper above, moving around is O(1) but update is O(log
n). This is acceptable; also because I'm quite confident that a zipper
for a 2D grid with everything O(1) does not exist. I can prove that for
a special case and should probably write it down at some point.

In other words, I suggest representing your grid as a

   Data.Map (Integer,Integer) a

and accept the minor inconvenience of a O(log n) update. Choosing a
different finite map implementation may give a better constant factor.
For instance you can nest two  Data.IntMap  etc.


> Righty right, but there's still the possibility that given all the 
> time in the world and the clearest explanations I'm just to dense to
> get a hold of it. That said I hope that's not the case but I might
> still be better off timewise to just go with MVars and a
> straightforward way first and then doing the reading and
> maybe refactoring to a different approach.

My personal experience is that not going with the obvious but messy
solution but searching for a more elegant one is always faster in the
long run. :)


Regards,
H. Apfelmus