2006/3/15, Paul Johnson <paul@cogito.org.uk>:
"minh thu" <noteed@gmail.com> wrote:
2006/3/15, Duncan Coutts <duncan.coutts@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_str...
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.
hi, to be clear, the data structure i'm thinking of is the "half edge" or "winged edge" : data structures to represent a 3d mesh in 3d modeling apps (thus, a constraint is that it can handle lot of data and fast updates). the idea of creating the data structure in plain c (and maybe the basic functions) and then use it (them) in haskell is bad ? thanks, vo minh thu