Re: [Haskell-cafe] 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).
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
Re: [Haskell-cafe] 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 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. Instead of lists of neighbouring nodes I might as well save the paths through the graphs separately from the nodes although I only have a very vague intuition about how that would look like. And instead of calculating a lists of nodes to update, I could calculate a path visting the nodes and update them (again beeing unable to escape from the prison of an imperative mindset) traversing the path. A zipper indeed allows you to move to neighbors and update them. But the point was that I just had a hard time generalizing what I read about zippers to structures where you can have embedded cycles, e.g. up . left . down . right = id. If you interpret zippers as the original data structure with a hole, this is not so difficult. For instance, consider a rectangular grid +--+--+--+--+--+--+--+ | | | | | | | | +--+--+--+--+--+--+--+ | | | | | | | | +--+--+--+--+--+--+--+ | | | | | | | | +--+--+--+--+--+--+--+ where you store some data at every node. Now, a zipper is just the old data structure but one node is marked as hole +--+--+--+--+--+--+--+ | | | | | | | | +--+--+--O--+--+--+--+ | | | | | | | | +--+--+--+--+--+--+--+ | | | | | | | | +--+--+--+--+--+--+--+ If you represent the grid as a rectangular table type Position = (Integer, Integer) type Grid a = Data.Map Position a a zipper is simply the grid with an extra marker type Zipper a = (Grid a, Position) left,right,up,down :: Zipper a - Zipper a left (g,(x,y)) = (g,(x-1,y)) right (g,(x,y)) = (g,(x+1,y)) up(g,(x,y)) = (g,(x,y-1)) down (g,(x,y)) = (g,(x,y+1)) update :: a - Zipper a - Zipper a update a (g,(x,y)) = (insert (x,y) a g, (x,y)) Note that the left, right etc. are not baked into the data type but implemented as normal functions. In principle, the same could be done for lists type ZipperL a = ([a], Int) left, right :: ZipperL a - ZipperL a left (xs,i) = (xs,i-1) right (xs,i) = (xs,i+1) update :: a - ZipperL a - ZipperL a update a (xs,i) = (take i xs ++ [a] ++ drop (i+1) xs, i) This is a valid implementation of a zipper for lists, but of course is very inefficient, update is O(n) . The key thing about the original list zipper with back and front list is that all operations are O(1). 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. In other words, I suggest representing your grid as a Data.Map (Integer,Integer) a and accept the minor inconvenience of a O(log n) update. Choosing a different finite map implementation may give a better constant factor. For instance you can nest two Data.IntMap etc. Righty right, but there's still the possibility that given all the time in the world and the clearest explanations I'm just to dense to get a hold of it. That said I hope
Re: [Haskell-cafe] 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. Now I understand, that that might very well be possible with zippers. Instead of lists of neighbouring nodes I might as well save the paths through the graphs separately from the nodes although I only have a very vague intuition about how that would look like. And instead of calculating a lists of nodes to update, I could calculate a path visting the nodes and update them (again beeing unable to escape from the prison of an imperative mindset) traversing the path. 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. That's right. After I wrote I that I realized that the distinction I made was a little bit of nonsense since a linear structure is a degenerated case of a tree like structure. But the point was that I just had a hard time generalizing what I read about zippers to structures where you can have embedded cycles, e.g. up . left . down . right = id. 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. ;) Righty right, but there's still the possibility that given all the time in the world and the clearest explanations I'm just to dense to get a hold of it. That said I hope that's note the case but I might still be better off timewise to just go with MVars and a straightforward way first and then doing the reading and maybe refactoring to a different approach. cheers Stephan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] 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 than to think about this stuff for the rest of my life. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] 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) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
