[Haskell-cafe] Re: dynamic arrays

[Jared Updike]

(Moved to haskell-cafe)

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

Hmmm, that is a problem, especially as you said, for enum types that
are bounded above. I guess you can't make it grow more than the min
and max. For the most part, this dynamic array would only be useful
for arrays with indices isomorphic to the natural numbers.

> 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

Perhaps the function to build these DynamicArrays could take a Maybe
parameter telling the maximum possible range (for bounded enums) or
Nothing if the array is allowed to grow indefinitely. Or an Either
parameter where Left (a,a) tells the max range and Right (a,a) ->
(a,a) which tells how the range should grow on a resize.

Or just the range resize function :: (a,a) -> (a,a) telling how to
grow on a resize, i.e. for enums function = id. Something like that.

  Jared.