[Haskell] Re: Haskell Digest, Vol 31, Issue 15
paul at cogito.org.uk
Wed Mar 15 16:38:36 EST 2006
"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:
>thanks, but I cannot construct the whole sturcture in one time (i need
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.
More information about the Haskell