[Haskell] Re: Haskell Digest, Vol 31, Issue 15

[Jared Updike]

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