[Haskell] implementing pointers-based data structure

[Sebastian Sylvan]

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...

/S

--
Sebastian Sylvan
+46(0)736-818655
UIN: 44640862