[Haskell-cafe] Re: Updating doubly linked lists

Apfelmus, Heinrich apfelmus at quantentunnel.de
Thu Jan 1 05:03:56 EST 2009

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


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

H. Apfelmus

More information about the Haskell-Cafe mailing list