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