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 ")-:"

2006/3/17, Bulat Ziganshin <bulat.ziganshin@gmail.com>:

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

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.