[Haskell] implementing pointers-based data structure

[minh thu]

2006/3/15, Duncan Coutts <duncan.coutts at worc.ox.ac.uk>:
> On Wed, 2006-03-15 at 17:21 +0100, Sebastian Sylvan wrote:
> > On 3/15/06, minh thu <noteed at gmail.com> wrote:
> > > hi everybody,
> > >
> > > i have to implement some data structure which is usually implemented
> > > with pointers in imperative languages (can think of it as a double
> > > linked list).
> > >
> > > i'd like to know how i have to do that.
> > >
> > > is there any standard way of converting pointer-based data structure
> > > into an inductively-defined data type (like standard haskell list) ?
> > > is-it possible ?
> > >
> > > or would it be good to define the data structure in c and write a
> > > haskell wrapper around the c code ?
> > >
> > > thank you a lot, bye,
> > > vo minh thu
> >
> > You can use references, IO, ST or STM.
> >
> > 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).

... there is a small mistake at slide 8 :  mkList [x] = Node ***x*** Nil Nil

again, thanks,
mt