implementing pointers-based data structure
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
On 3/15/06, minh thu <noteed@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
On 3/15/06, Sebastian Sylvan <sebastian.sylvan@gmail.com> wrote:
On 3/15/06, minh thu <noteed@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
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
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 ")-:"
On Wed, 2006-03-15 at 17:21 +0100, Sebastian Sylvan wrote:
On 3/15/06, minh thu <noteed@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_str... Duncan
2006/3/15, Duncan Coutts <duncan.coutts@worc.ox.ac.uk>:
On Wed, 2006-03-15 at 17:21 +0100, Sebastian Sylvan wrote:
On 3/15/06, minh thu <noteed@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_str...
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
participants (4)
-
Duncan Coutts -
Jared Updike -
minh thu -
Sebastian Sylvan