implementing pointers-based data structure

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

implementing pointers-based data structure

Vo Minh Thu
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
_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
Reply | Threaded
Open this post in threaded view
|

Re: implementing pointers-based data structure

Sebastian Sylvan
On 3/15/06, minh thu <[hidden email]> 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
_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
Reply | Threaded
Open this post in threaded view
|

Re: implementing pointers-based data structure

Sebastian Sylvan
On 3/15/06, Sebastian Sylvan <[hidden email]> wrote:

> On 3/15/06, minh thu <[hidden email]> 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
>

Eh? I forgot the constructors in the data type (in all three places!) :-)

data DLink a = Node (DLink a) a (DLink a) | Nil

test = d1
  where d1 = Node Nil 5 d2
            d2 = Node d1 6 Nil

/S
--
Sebastian Sylvan
+46(0)736-818655
UIN: 44640862
_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
Reply | Threaded
Open this post in threaded view
|

Re: implementing pointers-based data structure

Jared Updike
You could check out the data structures in Edison, a library of myriad
functional data structures. It may already have implemented a sequence
data structure with the desired features:
   http://www.eecs.tufts.edu/~rdocki01/docs/edison/index.html
homepage:
  http://www.eecs.tufts.edu/~rdocki01/edison.html

Cheers
  Jared.
--
http://www.updike.org/~jared/
reverse ")-:"
_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
Reply | Threaded
Open this post in threaded view
|

Re: implementing pointers-based data structure

Duncan Coutts
In reply to this post by Sebastian Sylvan
On Wed, 2006-03-15 at 17:21 +0100, Sebastian Sylvan wrote:

> On 3/15/06, minh thu <[hidden email]> 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

_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
Reply | Threaded
Open this post in threaded view
|

Re: implementing pointers-based data structure

Vo Minh Thu
2006/3/15, Duncan Coutts <[hidden email]>:

> On Wed, 2006-03-15 at 17:21 +0100, Sebastian Sylvan wrote:
> > On 3/15/06, minh thu <[hidden email]> 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
_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell