[Haskell-cafe] Re: Updating doubly linked lists

[S. Günther]

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