[Haskell-cafe] Updating doubly linked lists

[S. Günther]

G'Day,

and phew... quite a lot of code to grok. Thanks for the answers, they're much
appreciated.

On Sun, Jan 4, 2009 at 1:43 AM, Niklas Broberg <niklas.broberg at gmail.com> wrote:
>
> What you need is for the nodes to keep track of the length of the
> list. Here's a different solution from that oleg posted, to me it's
> slightly more intuitive, since the updates work directly on the dlists
> instead of via (elegant) proxy functions.
>
I had exactly the same thoughts after I realized that, if one wants to
update only
the non cyclic part of the list one has to know where the non cyclic
part ends. But
the only way to know that, is by keeping track of the length of the
list and using
this to find out when to tie the knot. So your solution is also more
intuitive to
me but if I'm not mistaken it has update complexity linear in the number of
elements in the list whereas Oleg's solution is logarithmic.

> mkRestDList :: Int -> [a] -> DList a -> DList a -> (DList a, DList a)
> mkRestDList _ []  _ farRight =
>    (farRight, farRight) -- will only happen if the initial list is singleton
> mkRestDList len [x] nearLeft farRight =
>    let this = DNode len nearLeft x farRight
>     in (this, this)
> mkRestDList len (x:xs) nearLeft farRight =
>    let this = DNode len nearLeft x nearRight
>        (nearRight,farLeft) = mkRestDList len xs this farRight
>     in (this,farLeft)
>
> updateRestD :: Int -> DList a -> DList a -> DList a -> (DList a, DList a)
> updateRestD 0 _ _ farRight =
>    (farRight, farRight) -- will only happen if the initial list is singleton
> updateRestD 1 (DNode len _ x _) nearLeft farRight =
>    let this = DNode len nearLeft x farRight in (this, this)
> updateRestD n (DNode len _ x r) nearLeft farRight =
>    let this = DNode len nearLeft x nearRight
>        (nearRight,farLeft) = updateRestD (n-1) r this farRight
>     in (this,farLeft)
> updateRestD _ Empty _ _ = undefined -- can't happen
>
I think you can drop the second case in those two functions if you rewrite the
first case like this:
mkRestDList _ []  nearLeft farRight = (farRight, nearLeft)
resp.
updateRestD 0 _ nearLeft farRight = (farRight, nearLeft)


On Sat, Jan 3, 2009 at 8:51 PM,  <oleg at okmij.org> wrote:
>
> Stephan Guenther wrote:
>
> The algorithm is essentially imperative (and so permits identity
> checking and in-place `updates') but implemented purely
> functionally. No destructive updates are ever used. Therefore, all the
> changes can be undone and re-done, and the code is MT-safe. The code
> is easily generalizable to 2D.
Thanks for your answer. As I'll explain below I also thought about
using a Map for
the 2D case, but wouldn't have thought of it in the one dimensional case as my
intuition would have been to use Niklas' solution there. Thanks for putting my
thoughts in a different direction.
Yet the thing that really puzzled me in the list case was, that I was
searching for
a solution without using auxiliary data like the length or delegating
the update to a
data structure which already supported it. I'm pretty sure by now that its
impossible without using zippers or something else.
> It is not for nothing Haskell is called the best imperative
> language. One can implement imperative algorithms just as they are --
> purely functionally, without any monads or other categorical notions.
Amen to that.

> -- The insert operation below makes a cyclic list
> -- The other operations don't care
> -- Insert to the right of the current element, if any
> -- Return the DL where the inserted node is the current one
> insert_right :: a -> DList a -> DList a
> insert_right x dl | is_empty dl =
>   let ref = dl_counter dl
>       -- the following makes the list cyclic
>       node = Node{node_val = x, node_left = ref, node_right = ref}
>   in DList{dl_counter = succ ref,
>            dl_current = ref,
>            dl_mem = IM.insert ref node (dl_mem dl)}
>
> insert_right x dl at DList{dl_counter = ref, dl_current = curr, dl_mem = mem} =
>  DList{dl_counter = succ ref, dl_current = ref,
>        dl_mem = IM.insert ref new_node $ IM.insert curr curr_node' mem}
>  where
>  curr_node = get_curr_node dl
>  curr_node'= curr_node{node_right = ref}
>  new_node  = Node{node_val   = x, node_left = curr,
>                  node_right = node_right curr_node}
Could it be that there's a small inconsistency in the fact that if you
don't update the
left_node ref of curr_node? This is nearly never a problem except when you do
insert_right on a DList with only one element. In that case node_left
of curr_node
references itself and should be updated to reference it's new right
(and therefore
also left wraparound) neighbour. If I'm right this leads to the fact
that DList is only
right cyclic while the left end always wraps around to itself.
I know that this is easily corrected (if wanted), I just want to know if I'm
understanding the code correctly.

On Sat, Jan 3, 2009 at 10:37 PM, Apfelmus, Heinrich
<apfelmus at quantentunnel.de> wrote:
> Ah, so you have a rectangular (or later hexagonal?) 2D grid? I suggest
> representing it as
>
>  Data.Map (Integer, Integer) a
>
> as explained below.
Right on the button. This is exactly what I need. And I also contemplated doing
it with indexing into Data.Map but decided against it because of the lookup
complexity. It might very well be the case that this is a non issue
but I'd rather
not loose the O(1) neighbour lookup and O(1) update. OTOH hand I'm aware
of the fact that using TVars very well might hurt performance if I'm not careful
with my transactions since the way TVars are managed would give me worse
complexity again. So for now I'm going with TVars while still keeping in mind
to maybe try the Data.Map approach later to see how it pans out.

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

I would be pretty interested in the proof, since when I was trying to
generalize
zippers I wanted to keep the nice O(1) on everything. And that was exactly
what I couldn't bring together with non trivial cycles.
I should point out that this is the point where my thoughts diverged. With the
doubly linked list example I wasn't concerned with performance I just wanted
to figure out a way to do updates in on circular DLists with proper sharing and
no additional data or data structures.
With my real world needs i.e. the 2D example I wanted to find a way to keep the
performance while remaining pure.

> 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. :)
Not only that but I also have the slight feeling that haskell would
reward me for
choosing the Data.Map approach. But I need a little bit of training on
TVars and
STM anyways so I'm going for this. For now that is. ;)

Big thanks. I already learned a lot from this thread.

Cheers
Stephan