[Haskell-cafe] Re: Updating doubly linked lists

[Apfelmus, Heinrich]

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

Ah, so you're using a sparse representation for grids. That's a good
idea! Unfortunately, it doesn't help when the grid is a full rectangle,
i.e. when nk(r) becomes proportional to r.

The (most likely unattainable) goal I had in mind is to create a zipper
for the full grid that supports O(1) operations.

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

Oh, right.

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

Well, that's still linear in the side length of a full grid. Directly using

   Data.Map (Integer,Integer) a

would improve that to a logarithm. Of course, your structure can be
enhanced by using a  Data.Map  instead of a linked list for each ring à la

   [Data.Map Integer a]

This will give O(log nk(r)) movements, but that's still not constant time.


Regards,
H. Apfelmus