(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.
Jared Updike wrote:
(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.
If I may make a suggestion: I think you have identified a need for certain operations which would benefit from a typeclass. The dynamic arrays need new operations on their indices, so they need a more specific type than Ix: class (Ix i) => IxDynamic i where expandSize :: (i,i) -> (i,i) dimensions :: i -> Int instance IxDynamic Int where expandSize (lower,upper) = (lower, 2*(upper-lower+1)+lower-1) dimensions _ = 1 instance (Num i,IxDynamic i,Num j, IxDynamic j) => IxDynamic (i,j) where expandSize ((low1,low2),(up1,up2)) = ((low1,low2),(2*(up1-low1+1)+low1-1,2*(up2-low2+1)+low2-1)) dimensions (a,b) = dimensions a + dimensions b -- This allows one to write expandVector, for instance: data (IxDynamic i) => Vector a i e = Vector (a i e) -- data (MArray a e m, IxDynamic i) => Vector m a i e = Vector (a i e) expandVector (Vector s) = do let a = bounds s b = expandSize b t <- newArray_ b mapM_ (uncurry (writeArray t)) =<< getAssocs s return (Vector t)
Hello Chris, Friday, March 17, 2006, 10:31:28 PM, you wrote: CK> If I may make a suggestion: I think you have identified a need for certain CK> operations which would benefit from a typeclass. The dynamic arrays need new CK> operations on their indices, so they need a more specific type than Ix: the *small* problem is what writeArray and all other operations defined with Ix in its head, so it's impossible to use in implementation any operations not in the Ix dictionary! The problem, after all, is what the MArray typeclass DON'T INCLUDES index type ibn its head, so i can't define something like: instance (IxDynamic i) => MArray DynamicIOArray i e IO ... and NOT making dynamic arrays an MArray instance is total useless in my opinion (and at least can be done by anyone without changing the arrays library). on the other side, changing MArray interface arity (number of parameters) will lead to changing declarations for all routines what acquire MArray parameters. so i still look for more oldcode-compatible solutions -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
Hello Chris, Friday, March 17, 2006, 10:31:28 PM, you wrote:
i tried to implement this today :) but there is one problem:
i've uploaded current version as http://freearc.narod.ru/ArrayRef.tar.gz see the Dynamic.hs usage example and Data/Array_/Dynamic.hs implementation module for details -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
Hello Jared, Friday, March 17, 2006, 9:11:43 PM, you wrote: JU> Or just the range resize function :: (a,a) -> (a,a) telling how to JU> grow on a resize, i.e. for enums function = id. Something like that. yes, i implemented this, and it even works :) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
participants (4)
-
Bulat Ziganshin -
Chris Kuklewicz -
Chris Kuklewicz -
Jared Updike