[Haskell-cafe] Re: Updating doubly linked lists

[Dan Weston]

Apfelmus,

Thanks for the reply.

 >>From your description (without reading the code ;))

I hope the code is better than my description! :) The structure is more like

Nothing(RK 0 _)
   Nothing(RK 1 _)
     A(RK 2 4)
       B(RK 3 6)
     C(RK 2 0)

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

No. The tree is [[Node]], where the outer list has one element for each 
radius that has an occupied node and each inner list has the number of 
nodes at the given radius.

You descend the spine of the outer list radially in O(deltaR) time, 
which for incremental moves is O(1).

Then you search for an existing inner list element in O(nk(r)), which 
stays fairly constant for reasonable paths (basically, the width of a 
path swath).

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

d is not the distance from the origin, it is nk(r), the number of nodes 
at a given radius: d(2) = 2, d(3) = 1.

An outward radial path will only expand the tree linearly, not 
quadratically, in size.

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

The parent of C is either A or B, depending on the path that created it, 
but parent teleports you in O(1).

Walking from A to B only involves:

(bX,bY) = (-3,0)
(aX,aY) = (-2,0)
(bR,bK) = (|bX| + |bY|, bR - bX) = (3,6) -- left halfplane
(aR,aK) = (|aX| + |aY|, aR - aX) = (2,4) -- left halfplane
deltaR  = bR - aR = 1
maybe (insertDownFirst (newNode rk) z) (moveAround rk) $ firstChild z

When firstChild fails, insertDownFirst and we're done! All operations 
are O(1).

When firstChild succeeds, moveAround queries each of the defined nodes 
-- but not any of the undefined nodes! -- at that radius. There is at 
most one defined node with Nothing value to ensure a path from the 
origin to every node (where path is not contiguous in X,Y, or K, only in R!)

The diagram you describe can be created with:

Prelude> :l GridZipper
*GridZipper> let f &&& g  = \x -> (f x, g x)
*GridZipper> let f >>> g  = g . f
*GridZipper> const (newGrid :: Grid String) >>> fromTree
  >>> west >>> west >>> setValue (Just "A: X=-2,Y=0,R=2,K=4")
  >>> west          >>> setValue (Just "B: X=-3,Y=0,R=3,K=6")
  >>> east >>> east >>> east
  >>> east >>> east >>> setValue (Just "C: X= 2,Y=0,R=2,K=0")
  >>> assocList >>> show >>> putStrLn $ ()

-- The tree is this:

[(XY (-2) 0,"A: X=-2,Y=0,R=2,K=4"),
  (XY (-3) 0,"B: X=-3,Y=0,R=3,K=6"),
  (XY   2  0,"C: X= 2,Y=0,R=2,K=0")]

-- Zipper starts at origin:

Loc
  {tree = Node {rootLabel = GridLabel (RK 0 0) Nothing,
   subForest = []}, lefts = [], rights = [], parents = []}


-- Zipper after walking to A and setting value:

Loc
  {tree = Node {rootLabel = GridLabel (RK 2 4)
                  (Just "A: X=-2,Y=0,R=2,K=4"),
   subForest = []},
  lefts   = [],
  rights  = [],
  parents = [([],GridLabel (RK 1 2) Nothing,[])
            ,([],GridLabel (RK 0 0) Nothing,[])]}

-- Zipper after walking to B and setting value:

Loc
  {tree = Node {rootLabel = GridLabel (RK 3 6)
                    (Just "B: X=-3,Y=0,R=3,K=6"),
   subForest = []},
  lefts   = [],
  rights  = [],
  parents = [([],GridLabel (RK 2 4)
                    (Just "A: X=-2,Y=0,R=2,K=4"),
         []),([],GridLabel (RK 1 2) Nothing,[])
            ,([],GridLabel (RK 0 0) Nothing,[])]}




-- Zipper where it left off at C:
(Loc
  {tree = Node {rootLabel = GridLabel (RK 2 0)
                           (Just "C: X=2,Y=0,R=2,K=0"),
   subForest = []},
   lefts   = [],
   rights  = [],
   parents = [([Node {rootLabel = GridLabel (RK 1 2) Nothing,
   subForest = [Node {rootLabel = GridLabel (RK 2 4)
                                 (Just "A: X=-2,Y=0,R=2,K=4"),
   subForest = [Node {rootLabel = GridLabel (RK 3 6)
                                 (Just "B: X=-3,Y=0,R=3,K=6"),
   subForest = []}]}]}],          GridLabel (RK 1 0) Nothing,[]),
                              ([],GridLabel (RK 0 0) Nothing,[])]},

-- Zipper at origin

Loc
  {tree      =  Node {rootLabel = GridLabel (RK 0 0) Nothing,
   subForest = [Node {rootLabel = GridLabel (RK 1 2) Nothing,
   subForest = [Node {rootLabel = GridLabel (RK 2 4)
                                (Just "A: X=-2,Y=0,R=2,K=4"),
   subForest = [Node {rootLabel = GridLabel (RK 3 6)
                                (Just "B: X=-3,Y=0,R=3,K=6"),
   subForest = [] } ]} ]},
                Node {rootLabel = GridLabel (RK 1 0) Nothing,
   subForest = [Node {rootLabel = GridLabel (RK 2 0)
                                 (Just "C: X=2,Y=0,R=2,K=0"),
   subForest = [] }] }]},
   lefts   = [],
   rights  = [],
   parents = []})



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