"minh thu" <[EMAIL PROTECTED]> wrote:
2006/3/15, Duncan Coutts <[EMAIL PROTECTED]>:
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.
_______________________________________________
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
