[Haskell] Re: Haskell Digest, Vol 31, Issue 15

[Paul Johnson]

"minh thu" <noteed at gmail.com> wrote:

>2006/3/15, Duncan Coutts <duncan.coutts at worc.ox.ac.uk>:
>  
>
>>On Wed, 2006-03-15 at 17:21 +0100, Sebastian Sylvan wrote:
>>    
>>
>>>You can also use laziness (untested!):
>>>
>>>data DLink a = (DLink a) a (DLink a) | Nil
>>>
>>>test = d1
>>>  where d1 = Nil 5 d2
>>>            d2 = d1 6 Nil
>>>
>>>test here is a linked list containing 5 and the next node containing
>>>6. Both nodes have references to the next and previous links (wich is
>>>Nil at the ends). The magic here is laziness. You reference d2 in the
>>>definition for d1 and d1 in the definition for d2. It gets sort of
>>>clumsy to work with, though. You're probably better off using STRefs
>>>(for example) if you really need that type of data structures...
>>>      
>>>
>>I wrote a talk once on this topic:
>>http://web.comlab.ox.ac.uk/oucl/work/duncan.coutts/papers/recursive_data_structures_in_haskell.pdf
>>
>>Duncan
>>    
>>
>thanks, but I cannot construct the whole sturcture in one time (i need
>incremental update).
>  
>
You might also go back and think about why you needed that double linked 
list in the first place.  Many things that require complicated list 
structures in C are better represented as compositions of functions.  
The simplest example is StringS in the Standard Prelude, which avoids 
O(n^2) behaviour in list concatenation by composing functions instead.  
Similarly you might find that by representing your data structure as the 
composition of the functions needed to build it you can defer creation 
of the actual structure to the point at which it gets read.  Then all 
the closures get evaluated, but the evaluated stuff stays around and 
acts as the foundation for subsequent updates.  It all depends on what 
you want to do.

I suggest reading Chris Okasaki (sp?) on the subject.

Paul.