Also, it's actually really hard to tie the knot in the update; without some kind of distinguished node that allows you to know that it is the beginning/end of the list. For example, in this DList: 1,1,1, .... lots of times, 1, 2, 1, 1, ... lots of times, 1, (loop) If you change the 3rd "1", how do you know when to tie the knot and attach the list back together? This is a big problem with knot-tied datastructures in Haskell; it's very difficult to *untie* the knot and find the ends of the string again! Another example:
-- constant space no matter how many elements you access list_1 = repeat 1 :: [Int]
-- blows up to infinite size even though it's just "repeat (1 + 1)" list_2 = map (+1) list_1
--ryan
On Wed, Dec 31, 2008 at 5:07 AM, Martijn van Steenbergen
Hi Stephan,
S. Günther wrote:
Is it possible to change a particular node of the doubly linked list? That is to say, that would like to have a function: update :: DList a -> a -> DList a where update node newValue returns a list where only the value at the node which is passed in is set to the new Value and all other values are the same. All this of course in a pure way, that is without using (M/T/TM)Vars or IORefs.
The short answer is: yes, but the complete DList structure will need to be built anew (if nodes in the updated list are needed).
The longer answer is: Because everything is pure, 'update' will need to create a new DLNode with the new value. But then you will also want to update the node's neighbours to point to the newly created DLNode, because if you don't then moving forward and then backward one position would make you end up at the old value again. But to update the neighbours' links to the new node you need to create new neighbour DLNodes, because everything is pure. And so on, until the whole list has been recreated.
To not need to recreate the whole list you will need some kind of assignment, and this is exactly what vars/refs are for.
Hope this helps,
Martijn. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe