[Haskell-cafe] Updating doubly linked lists

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