"minh thu" <[hidden email]> wrote:
>2006/3/15, Duncan Coutts <[hidden email]>: > > >>On Wed, 2006-03-15 at 17:21 +0100, Sebastian Sylvan wrote: >> >> >>>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). > > list in the first place. Many things that require complicated list structures in C are better represented as compositions of functions. The simplest example is StringS in the Standard Prelude, which avoids O(n^2) behaviour in list concatenation by composing functions instead. Similarly you might find that by representing your data structure as the composition of the functions needed to build it you can defer creation of the actual structure to the point at which it gets read. Then all the closures get evaluated, but the evaluated stuff stays around and acts as the foundation for subsequent updates. It all depends on what you want to do. I suggest reading Chris Okasaki (sp?) on the subject. Paul. _______________________________________________ Haskell mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell |
2006/3/15, Paul Johnson <[hidden email]>:
> "minh thu" <[hidden email]> wrote: > > >2006/3/15, Duncan Coutts <[hidden email]>: > > > > > >>On Wed, 2006-03-15 at 17:21 +0100, Sebastian Sylvan wrote: > >> > >> > >>>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). > > > > > You might also go back and think about why you needed that double linked > list in the first place. Many things that require complicated list > structures in C are better represented as compositions of functions. > The simplest example is StringS in the Standard Prelude, which avoids > O(n^2) behaviour in list concatenation by composing functions instead. > Similarly you might find that by representing your data structure as the > composition of the functions needed to build it you can defer creation > of the actual structure to the point at which it gets read. Then all > the closures get evaluated, but the evaluated stuff stays around and > acts as the foundation for subsequent updates. It all depends on what > you want to do. > to be clear, the data structure i'm thinking of is the "half edge" or "winged edge" : data structures to represent a 3d mesh in 3d modeling apps (thus, a constraint is that it can handle lot of data and fast updates). the idea of creating the data structure in plain c (and maybe the basic functions) and then use it (them) in haskell is bad ? thanks, vo minh thu _______________________________________________ Haskell mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell |
General question to the list:
(Q) Are there any data structures in Haskell similar to C++/STL vectors or C# generic Lists (i.e. strongly typed ArrayLists, e.g. List<int>)? These data structures grow automatically as you add elements to them (but in large chunks, not one node at a time). This data structure (if it exists in Haskell) would run inside a monad (ST and/or IO) and it would automaticly resize when needed, but would be more or less like a mutable array except you can add new elements to the end of it without reallocating an entire array of n+1 elements... > hi, > to be clear, the data structure i'm thinking of is the "half edge" or > "winged edge" : data structures to represent a 3d mesh in 3d modeling > apps (thus, a constraint is that it can handle lot of data and fast > updates). Instead of pointers I would use integer offsets into an array of vertices. Unboxed arrays should help here. (I know when I coded a winged edge library in C++ I used indices to vertices instead of pointers, I think...) You can update mutable arrays in place (inside the ST or IO monad, of course), though I haven't had time to play with this: http://haskell.org/haskellwiki/Arrays This would be a lot more effective than lists or even doubly linked lists (mutable array access time = O(1), update time = O(1)). You could accumulate your vertices into a list and then freeze it into an array. If you need to add vertices to your array after you create it, you will need a data type like I mentioned at the (Q) above (if it exists). > the idea of creating the data structure in plain c (and maybe the > basic functions) and then use it (them) in haskell is bad ? This might be possible, but I don't think that C has the right type of data structure, either (though certainly you could create it). Ideally you want something like C++ vectors or C# generic Lists if you need the ability to augment it. If you make the datastructures and functions in C you'd still have to wrap these functions in a monad like IO to make it safe (Which the Array libs do ... if they are the right datastructure for you.) but that's probably only a good idea if you can't find the right datastruct in Haskell. Jared. -- http://www.updike.org/~jared/ reverse ")-:" _______________________________________________ Haskell mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell |
Hello Jared,
Thursday, March 16, 2006, 11:35:24 PM, you wrote: JU> General question to the list: JU> (Q) Are there any data structures in Haskell similar to C++/STL JU> vectors or C# generic Lists (i.e. strongly typed ArrayLists, e.g. JU> List<int>)? These data structures grow automatically as you add JU> elements to them (but in large chunks, not one node at a time). This JU> data structure (if it exists in Haskell) would run inside a monad (ST JU> and/or IO) and it would automaticly resize when needed, but would be JU> more or less like a mutable array except you can add new elements to JU> the end of it without reallocating an entire array of n+1 elements... i tried to implement this today :) but there is one problem: if i have (l,u) - array bounds of type Ix, and i - offending index of the same type, how can i compute new bounds of array so that it will grow in large chunks? there is no such computation operations for Ix type and that is logical - if this array is really a matrix then it's hard to use the same rules of extending it as for vectors such computation as (u-l)*2+l is great for integral indexes, but not for general case. now i plan to use this strategy for all enum types and just "grow to minimal and maximal indexes actually used" for other index types -- Best regards, Bulat mailto:[hidden email] _______________________________________________ Haskell mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell |
2006/3/17, Bulat Ziganshin <[hidden email]>:
> Hello Jared, > > Thursday, March 16, 2006, 11:35:24 PM, you wrote: > > JU> General question to the list: > JU> (Q) Are there any data structures in Haskell similar to C++/STL > JU> vectors or C# generic Lists (i.e. strongly typed ArrayLists, e.g. > JU> List<int>)? These data structures grow automatically as you add > JU> elements to them (but in large chunks, not one node at a time). This > JU> data structure (if it exists in Haskell) would run inside a monad (ST > JU> and/or IO) and it would automaticly resize when needed, but would be > JU> more or less like a mutable array except you can add new elements to > JU> the end of it without reallocating an entire array of n+1 elements... > > i tried to implement this today [...mail cut here ...] hello, when you say you try to implement it, how do you do it ? c -> ffi -> haskell ? thanks, minh thu _______________________________________________ Haskell mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell |
2006/3/17, minh thu <[hidden email]>:
> 2006/3/17, Bulat Ziganshin <[hidden email]>: > > Hello Jared, > > > > Thursday, March 16, 2006, 11:35:24 PM, you wrote: > > > > JU> General question to the list: > > JU> (Q) Are there any data structures in Haskell similar to C++/STL > > JU> vectors or C# generic Lists (i.e. strongly typed ArrayLists, e.g. > > JU> List<int>)? These data structures grow automatically as you add > > JU> elements to them (but in large chunks, not one node at a time). This > > JU> data structure (if it exists in Haskell) would run inside a monad (ST > > JU> and/or IO) and it would automaticly resize when needed, but would be > > JU> more or less like a mutable array except you can add new elements to > > JU> the end of it without reallocating an entire array of n+1 elements... > > > > i tried to implement this today [...mail cut here ...] > > hello, > when you say you try to implement it, how do you do it ? c -> ffi -> haskell ? > > thanks, > minh thu > mt _______________________________________________ Haskell mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell |
In reply to this post by Vo Minh Thu
minh thu wrote:
> to be clear, the data structure i'm thinking of is the "half edge" or > "winged edge" this would involve a cyclic structure, and you want to update that. I don't think there's a purely functional way to implement that, and if there is, it wouldn't allow O(1) modifications. So it appears, you will have to mangle pointers. This is indeed possible, pointers in Haskell are spelled "STRef". > the idea of creating the data structure in plain c (and maybe the > basic functions) and then use it (them) in haskell is bad ? Do you honestly think that C is ever a good idea? Of course, you can write the data structure in C, but it will be essentially the same code you would write in Haskell using STRefs. Additionally you will get the usual off-by-one errors, dangling pointers and the ever helpful error message "killed by SEGSEGV". Udo. -- <Alanna> Saying that Java is nice because it works on all OS's is like saying that anal sex is nice because it works on all genders. _______________________________________________ Haskell mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell signature.asc (196 bytes) Download Attachment |
Free forum by Nabble | Edit this page |