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