[Haskell-cafe] Re: Updating doubly linked lists
Apfelmus, Heinrich
apfelmus at quantentunnel.de
Tue Jan 6 04:05:46 EST 2009
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
More information about the Haskell-Cafe
mailing list