[Haskell-cafe] Updating doubly linked lists

[S. Günther]

Thanks for the answers to all.
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

update :: DList a -> a -> DList a
update n newValue = n' where
  n' = DLNode (linkleft n n') newValue (linkright n n')

linkleft, linkright :: DList a -> DList a -> DList a
linkleft Leaf _ = Leaf
linkleft old new = l' where
  l  = left old
  l' = case l of {~Leaf -> l; _ -> l{left = linkleft l l', right = new}}


linkright Leaf _ = Leaf
linkright old new = r' where
  r  = right old
  r' = case r of {~Leaf -> r; _ -> r{right = linkright r r', left = new}}

Not the most elegant solution but relatively straightforward.
And it does what it should if the list is terminated with Leaves on
the left and
right. One can also run it on an circular list but then it just
doesn't work like
it should (which isn't surprising):

*T> let l = mkDList [1..5]
*T> takeF 11 l
[1,2,3,4,5,1,2,3,4,5,1]
*T> let l' = update l (-1)
*T> takeF 11 l'
[-1,2,3,4,5,1,2,3,4,5,1]

So my problem is whether it possible to implement update in a way that
makes takeF 11 l' return [-1,2,3,4,5,-1,2,3,4,5,-1], and if it is possible I
would appreciate any pointers on how because I just can't figure it out.
But I'm already thankful for the answers so far, especially for the pointer
to map (+1) (repeat (1::Int)) since I really didn't expect it to behave like
that. And I would like to apologize for being too short in the formulation of
my original question.

cheers
Stephan

On Thu, Jan 1, 2009 at 8:11 AM, Ryan Ingram <ryani.spam at gmail.com> wrote:
> 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
> <martijn at van.steenbergen.nl> wrote:
>> 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 at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>