Re: dynamic arrays

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

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.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: dynamic arrays

Chris Kuklewicz-2
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)
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: dynamic arrays

haskell-2
Small typo fix:

>
> expandVector (Vector s) = do
>   let a = bounds s
>       b = expandSize b

        b = expandSize a

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re[2]: dynamic arrays

Bulat Ziganshin-2
In reply to this post by Jared Updike
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:[hidden email]

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re[2]: Re: dynamic arrays

Bulat Ziganshin-2
In reply to this post by Chris Kuklewicz-2
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:[hidden email]

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re[2]: Re: dynamic arrays

Bulat Ziganshin-2
In reply to this post by Chris Kuklewicz-2
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:[hidden email]

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe