[Haskell-cafe] Re: Updating doubly linked lists

[Apfelmus, Heinrich]

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.


For more about zippers, see also

   http://en.wikibooks.org/wiki/Haskell/Zippers

There are also some ready-made packages on hackage, like  ListZipper .


Regards,
H. Apfelmus