[Haskell] Re: Haskell Digest, Vol 31, Issue 15
jupdike at gmail.com
Thu Mar 16 15:35:24 EST 2006
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...
> 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
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 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
> 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.
More information about the Haskell