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 |
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 |
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 |
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 |
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 |
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 |
Free forum by Nabble | Edit this page |