Editing Library/ArrayRef (section)

===Using dynamic (resizable) arrays===

Just to let you know - the current implementation of dynamic arrays is
very trivial: it just saves a reference (IORef or STRef) to the mutable
array. When a dynamic array is resized, a new mutable array is allocated and the
contents is copied. New elements are filled with the same default value as when
the array was created with the newArray
or newDynamicArray operation. If a dynamic array is created with
newArray_ or newDynamicArray_, then new elements will be left
undefined.

A dynamic array can be resized explicitly by the resizeDynamicArray operation:

<haskell>
  resizeDynamicArray array (l,u)
</haskell>

where (l,u) are new array bounds. If the dynamic array was created
by a newArray or newArray_ operation, it is the only way to resize it -
attempts to write beyond current bounds will raise an exception:

<haskell>
  arr <- newArray (0,-1) 99 :: IO (DynamicIOArray Int Int)
  resizeDynamicArray arr (0,0)
  writeArray arr 1 1  -- this operation raises an exception
</haskell>


To create an array that will be automatically resized on attempt to write
beyond current bounds, you should use a newDynamicArray or
newDynamicArray_ operation (the former initializes an array with a given value,
while the latter leaves the array uninitialized). Their first argument
determines the array expansion policy:

<haskell>
   arr <- newDynamicArray_ growTwoTimes (0,-1) :: IO (DynamicIOArray Int Int)
</haskell>

This array will grow to at least two times its current size, each time automatic
expansion occurs, which is determined by using the `growTwoTimes`
parameter. This parameter is just an ordinary function that has the
following type:

<haskell>
type GrowBoundsF i  =  (i,i) -> i -> (i,i)
</haskell>

This function accepts old array bounds and offending index and
returns new array bounds. You can write new functions for expansion
policies yourself, or use one of predefined ones:

 growTwoTimes - expand array to at least two times its current size
 growMinimally - minimal growth that ensures inclusion of new index
 noGrow - disable automatic growth. This policy is used for arrays created by newArray or newArray_

Please note that not every array can work with every expansion policy
and that is why I supported freedom of selection of this policy. Only
the noGrow policy is compatible with every index type. The growMinimally
policy by its type is compatible with any index, but it will not work
for partially ordered indexes, in particular for multi-dimensional
arrays. Imagine, for example, an array with the bounds (0,0)..(9,9). When you
try to write to index (15,5), this expansion policy function will
be unable to determine what the new bounds should be (0,0)..(15,9). So you
should always provide a custom expansion policy function for partially
ordered indexes. At last, the growTwoTimes policy is compatible only with
indexes belonging to class Num, but it is the most useful policy of all,
because it ensures that the program will not spend all its
time expanding arrays. On the other hand, you can provide your own
policy function that will, for example, expand an array only 1.5 times.

Dynamic arrays support the same MArray and HasMutableBounds interfaces
as other mutable arrays, but they don't support the HasBounds interface.


And now about types of dynamic arrays. These types reflect all the
types you can use for mutable arrays, and include DynamicIOArray,
DynamicIOUArray, DynamicSTArray, DynamicSTUArray, which have the
same parameters as corresponding arrays without the "Dynamic" prefix.
Some examples are:

<haskell>
  DynamicIOArray Int Double
  DynamicSTUArray s (Int,Int) Bool
</haskell>

You can also create dynamic arrays from other mutable array types
working in the IO monad:

<haskell>
  DynamicIO StorableArray Int Double
</haskell>

or the ST monad:

<haskell>
  DynamicST s (STUArray s) (Int,Int) Bool
</haskell>

or any other monad (ask me if you need this). Btw, implementation of
dynamic arrays use the monad-independent references class mentioned
above.


See "Examples/Array/Dynamic.hs" for further examples on using these arrays.