[Haskell-cafe] Re: Updating doubly linked lists

[Dan Weston]

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

Really? My solution (rose tree zipper where tree depth is manhattan 
distance from origin and forest width is nodes around concentric 
diamonds, see 
http://permalink.gmane.org/gmane.comp.lang.haskell.cafe/49948) was 
designed specifically to be amortized constant for everything for paths 
that do not specifically move helically around the origin. The 
complexity of lookup is O(d) where d is the number of defined nodes at a 
given radius. Until the grid gets pretty dense, d grows very slowly for 
most sane paths.

Have I missed something?

Dan

Apfelmus, Heinrich wrote:
> 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
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>