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 that's not 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.
My personal experience is that not going with the obvious but messy
solution but searching for a more elegant one is always faster in the
long run. :)
Regards,
H. Apfelmus
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
