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

minh thu noteed at gmail.com
Thu Mar 16 08:04:01 EST 2006

2006/3/15, Paul Johnson <paul at cogito.org.uk>:
> "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.
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

the idea of creating the data structure in plain c (and maybe the
basic functions) and then use it (them) in haskell is bad ?

vo minh thu

More information about the Haskell mailing list