[Haskell-cafe] Re: Updating doubly linked lists

[Apfelmus, Heinrich]

Dan Weston wrote:
>> 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?

>From your description (without reading the code ;)), I gather that your
tree looks something like this?

             -+-
            /   \
          -+ -+- +-
         /  /   \  \
       -+ -+ -+- +- +-
      /  /  /   \  \  \
    -+ -+ -+ -+- +- +- +-
   /  /  /  /   \  \  \  \
  +  B  A  +  +--+--C--+--+-- ...
   \  \  \  \   /  /  /  /
    -+ -+ -+ -+- +- +- +-
      \  \  \   /  /  /
       -+ -+ -+- +- +-
         \  \   /  /
          -+ -+- +-
            \   /
             -+-

The root of the tree is the center and you can descend on the right. But
with this structure, walking from A to B is O(d) = O(n) (where d is the
distance from the origin, n the side length of the grid) instead of O(1).

Put differently, using  Data.Tree.Zipper.parent  on B will move you to
C, not to A.


I mean, O(d) may be fine for you, but it's not O(1) for everything as
advertised. :)


Regards,
H. Apfelmus