S. Günther | 1 Jan 04:14 2009

Re: Updating doubly linked lists

Thanks for the answers to all.
Untying the knot was (and still is) exactly the problem I was facing.
I knew that the whole list had to be rebuild and wasn't concerned
with performance since at that point I just wanted to know how to
do it and if it is possible at all. After I realized that it maybe just to
hard in the circular case I tried my hand on a non circular version
coming up with the following.
data DList a =
  DLNode {left::(DList a), value::a, right::(DList a)} |
  Leaf

update :: DList a -> a -> DList a
update n newValue = n' where
  n' = DLNode (linkleft n n') newValue (linkright n n')

linkleft, linkright :: DList a -> DList a -> DList a
linkleft Leaf _ = Leaf
linkleft old new = l' where
  l  = left old
  l' = case l of {~Leaf -> l; _ -> l{left = linkleft l l', right = new}}

linkright Leaf _ = Leaf
linkright old new = r' where
  r  = right old
  r' = case r of {~Leaf -> r; _ -> r{right = linkright r r', left = new}}

Not the most elegant solution but relatively straightforward.
And it does what it should if the list is terminated with Leaves on
the left and
right. One can also run it on an circular list but then it just
(Continue reading)

Apfelmus, Heinrich | 1 Jan 11:03 2009
Picon

Re: Updating doubly linked lists

S. Günther wrote:
> Untying the knot was (and still is) exactly the problem I was facing.
> I knew that the whole list had to be rebuild and wasn't concerned
> with performance since at that point I just wanted to know how to
> do it and if it is possible at all. After I realized that it maybe just to
> hard in the circular case I tried my hand on a non circular version
> coming up with the following.
>
> data DList a =
>   DLNode {left::(DList a), value::a, right::(DList a)} |
>   Leaf

Whether circular or not, sharing values by using a "back pointer" is
problematic for any update. Why not use a zipper instead?

    data Zipper a = Zip [a] a [a]

    value :: Zipper a -> a
    value (Zip _ x _) = x

    right, left :: Zipper a -> Zipper a
    left  (Zip (l:ls) x rs) = Zip ls l (x:rs)
    right (Zip ls x (r:rs)) = Zip (x:ls) r rs

    update :: Zipper a -> a -> Zipper a
    update (Zip ls _ rs) x = Zip ls x rs

In other words, you don't have to implement  left  and  right  as record
labels, implementing them as normal functions may be better.

(Continue reading)

S. Günther | 2 Jan 00:48 2009

Re: Re: Updating doubly linked lists

> Whether circular or not, sharing values by using a "back pointer" is
> problematic for any update. Why not use a zipper instead?
I looked into zippers before and the problem I had was that they never
really matched the structure which I needed and which led me to think
about this whole knot tying thing again.[1] The things I read about them
always assumed either a list like (i.e. linear) or a tree like (i.e. existence
of a root) structure on the type to be plugged into the zipper. Now I know
that this is not necessary and there are references to a generic zipper
implementation but the thing is that I only found the source code and
decided to first look into the knot tying thing before opening another
can of worms with delimited continuations since I already spend too
muchtime thinking about that stuff.[2] So if anyone has pointers to a
good generic zipper explanation I would be thankful. Note that I don't
need full blown error handling. I would first like to understand the basics.
Now I think I came to the conclusion that locally updating a tied knot in a
pure way really is hard and that it's not me just not seeing some obvious
solution. So I just have to decide whether to use IORefs/Vars (clunky)
or to implement zippers for the structure I need (probably toohard for me).
Anyways thanks for all the answers from which I learned a few unexpected
things and which assured me that my instincts aren't that far off.

Cheers and warm regards (and a happy new year)
Stephan

[1]: "Again" means that I already looked into both tying the knot and
zippers about a year ago out of curiosity. This time it was out of necessity
although the original question I posed was more a necessity diverging
into curiosity again.
[2]: Note that "too much time" rather refers to the quantity I have at my
disposal than to personal preferences. If I could I would like nothing more
(Continue reading)

Derek Elkins | 2 Jan 01:18 2009
Picon

Re: Re: Updating doubly linked lists

On Fri, 2009-01-02 at 10:48 +1100, S. Günther wrote:
> > Whether circular or not, sharing values by using a "back pointer" is
> > problematic for any update. Why not use a zipper instead?
> I looked into zippers before and the problem I had was that they never
> really matched the structure which I needed and which led me to think
> about this whole knot tying thing again.[1] The things I read about them
> always assumed either a list like (i.e. linear) or a tree like (i.e. existence
> of a root) structure on the type to be plugged into the zipper. Now I know
> that this is not necessary and there are references to a generic zipper
> implementation but the thing is that I only found the source code and
> decided to first look into the knot tying thing before opening another
> can of worms with delimited continuations since I already spend too
> muchtime thinking about that stuff.[2] So if anyone has pointers to a
> good generic zipper explanation I would be thankful. Note that I don't
> need full blown error handling. I would first like to understand the basics.
> Now I think I came to the conclusion that locally updating a tied knot in a
> pure way really is hard and that it's not me just not seeing some obvious
> solution. So I just have to decide whether to use IORefs/Vars (clunky)
> or to implement zippers for the structure I need (probably toohard for me).
> Anyways thanks for all the answers from which I learned a few unexpected
> things and which assured me that my instincts aren't that far off.

Read this http://strictlypositive.org/diff.pdf (again)
Apfelmus, Heinrich | 2 Jan 11:50 2009
Picon

Re: Updating doubly linked lists

S. Günther wrote:
>>
>> Whether circular or not, sharing values by using a "back pointer" is
>> problematic for any update. Why not use a zipper instead?
>
> I looked into zippers before and the problem I had was that they never
> really matched the structure which I needed and which led me to think
> about this whole knot tying thing again.

What kind of structure do you need exactly?

> The things I read about them
> always assumed either a list like (i.e. linear) or a tree like (i.e. existence
> of a root) structure on the type to be plugged into the zipper.

Viewing the zipper as the derivative of a data type opens up more
possibilities.

That being said, every algebraic data types has a tree-like structure.
The extra invariants like

   left . right  =  right . left

that the programmer imposes are what make them different from trees.

> So I just have to decide whether to use IORefs/Vars (clunky)
> or to implement zippers for the structure I need (probably too hard for me).

It's not too hard for you. You've got a whole haskell-cafe and #haskell
at your fingertips, after all. ;)
(Continue reading)

S. Günther | 3 Jan 01:39 2009

Re: Re: Updating doubly linked lists

There goes my promise like a new years resolution... ;)
> What kind of structure do you need exactly?
What I really need is a structure which represents a two dimensional
grid, i.e. it
consists of nodes having a value and a list of neighbours attached to
it. Point is
that if node 1 has node 2 as a neighbour then node 2 has to have node 1 as a
neighbour and each node has the same number of neighbours (currently 4, but
may vary). So it really is just an undirected planar graph with some
restrictions.
And it isn't even circular because nodes may have Leaves as neighbours
signalling that they are boundary nodes. And since the algorithm I
would like to
implement is specified in a purely imperative way I need to be able to
update the
values stored at the nodes and insert new nodes at where there a Leaves.
So I figured since the structure isn't even circular I could do it the
inefficient way
and just use a generalization of the update function for doubly linked
lists I came
up with before and thus always rebuild the whole structure.
That's why I said that thinking about the circular case was just a
divergence that
rally got me wondering/interested which is why I posted the question
in it's short
form at the beginning.
Anyways, back to the structure I need. One additional thing which will
happen during the algorithm is that there will be updates to a certain
local neighbourhood
of a node.
(Continue reading)

Apfelmus, Heinrich | 3 Jan 12:37 2009
Picon

Re: Updating doubly linked lists

S. Günther wrote:
>
>> What kind of structure do you need exactly?
>
> What I really need is a structure which represents a two dimensional 
> grid, i.e. it consists of nodes having a value and a list of
> neighbours attached to it. Point is that if node 1 has node 2 as a
> neighbour then node 2 has to have node 1 as a
> neighbour and each node has the same number of neighbours (currently
> 4, but may vary).

Ah, so you have a rectangular (or later hexagonal?) 2D grid? I suggest
representing it as

  Data.Map (Integer, Integer) a

as explained below.

> That's why I said that thinking about the circular case was just a
> divergence that really got me wondering/interested which is why I posted
> the question in it's short form at the beginning.

Exploring a related easier problem is always a good way to get some
intuition for tackling the harder one. :)

> Anyways, back to the structure I need. One additional thing which will
> happen during the algorithm is that there will be updates to a certain
> local neighboruhood of a node. Now I understand, that that might very
> well be possible with zippers.
>
(Continue reading)

Dan Weston | 6 Jan 00:59 2009

Re: Re: Updating doubly linked lists

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

Dan

Apfelmus, Heinrich wrote:
> S. Günther wrote:
>>> What kind of structure do you need exactly?
>> What I really need is a structure which represents a two dimensional 
>> grid, i.e. it consists of nodes having a value and a list of
>> neighbours attached to it. Point is that if node 1 has node 2 as a
>> neighbour then node 2 has to have node 1 as a
>> neighbour and each node has the same number of neighbours (currently
>> 4, but may vary).
> 
> Ah, so you have a rectangular (or later hexagonal?) 2D grid? I suggest
(Continue reading)

Apfelmus, Heinrich | 6 Jan 10:05 2009
Picon

Re: Updating doubly linked lists

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--+--+-- ...
(Continue reading)

Dan Weston | 6 Jan 22:25 2009

Re: Re: Updating doubly linked lists

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

(Continue reading)

Apfelmus, Heinrich | 7 Jan 10:55 2009
Picon

Re: Updating doubly linked lists

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.
(Continue reading)


Gmane