# Library/ArrayRef

### From HaskellWiki

(→Downloading and installation: characterize links better) |
|||

(11 intermediate revisions by 5 users not shown) | |||

Line 1: | Line 1: | ||

− | Arrays&References library supports | + | The Arrays&References library supports GHC 6.8.x (an older version supports Hugs 2003-2006 and GHC 6.4). It includes the following features: |

− | It includes the following features: | + | |

==Unboxed references== | ==Unboxed references== | ||

− | |||

This substitutes the numerous "fast mutable Ints", "fast mutable | This substitutes the numerous "fast mutable Ints", "fast mutable | ||

− | Bools" | + | Bools" and "fast mutable Ptrs" ghc-specific modules that are used in |

almost any large project. In contrast to them, this library mimics | almost any large project. In contrast to them, this library mimics | ||

− | well-known interface of IORef/STRef: | + | the well-known interface of IORef/STRef: |

+ | <haskell> | ||

import Data.Ref | import Data.Ref | ||

main = do x <- newIOURef (0::Int) | main = do x <- newIOURef (0::Int) | ||

writeIOURef x 1 | writeIOURef x 1 | ||

− | readIOURef x > | + | a <- readIOURef x |

+ | print a | ||

+ | </haskell> | ||

− | Unboxed references for IO monad | + | Unboxed references for the IO monad have the type "IOURef a" and operations |

− | newIOURef, readIOURef, writeIOURef. Unboxed references for ST monad | + | newIOURef, readIOURef, writeIOURef. Unboxed references for the ST monad |

− | + | have the type "STURef s a" and operations newSTURef, readSTURef, | |

writeSTURef. | writeSTURef. | ||

− | Unboxed references can | + | Unboxed references can only contain values of the following types: |

Bool, Char, Int, Int8..Int64, Word, Word8..Word64, Float, Double, | Bool, Char, Int, Int8..Int64, Word, Word8..Word64, Float, Double, | ||

− | Ptr a, FunPtr a, StablePtr a. These types are members of Unboxed class | + | Ptr a, FunPtr a, StablePtr a. These types are members of the Unboxed class |

and you can implement new instances of this class by converting values | and you can implement new instances of this class by converting values | ||

− | of some | + | of some other type (say, CChar) to values of an already supported type. |

Despite all these improvements, operations with unboxed references are | Despite all these improvements, operations with unboxed references are | ||

compiled to the same code as for any "fast mutable variables". Moreover, | compiled to the same code as for any "fast mutable variables". Moreover, | ||

− | unboxed references are available even for Hugs | + | unboxed references are available even for Hugs, which allows simplified |

− | debugging of programs that | + | debugging of programs that use them. Please note that unboxed references |

− | always hold computed values, in contrast to boxed references, | + | always hold computed values, in contrast to boxed references, which can |

− | contain unevaluated | + | contain unevaluated thunks. |

− | I wish to thank Simon Marlow and especially Oleg Kiselyov who | + | I wish to thank Simon Marlow and especially Oleg Kiselyov who proposed |

− | idea of these references and | + | the idea of these references and their implementation (in particular, see |

− | http://www.haskell.org/pipermail/haskell-cafe/2006-February/014324.html) | + | [http://www.haskell.org/pipermail/haskell-cafe/2006-February/014324.html]) |

You can find examples of using unboxed references in "Examples/URef.hs" | You can find examples of using unboxed references in "Examples/URef.hs" | ||

Line 42: | Line 43: | ||

==Monad-independent references== | ==Monad-independent references== | ||

− | Sometimes you need to write code that will be compatible | + | Sometimes you need to write code that will be compatible with both IO |

− | and ST monads, and even better with any monad that | + | and ST monads, and even better with any monad that is lifted from |

one of these two. This is especially useful for writing library code that | one of these two. This is especially useful for writing library code that | ||

should be as generic as possible. Operations for arrays, for example, | should be as generic as possible. Operations for arrays, for example, | ||

− | are ready for such | + | are ready for such a kind of usage - readArray and writeArray can work |

− | in any monad. But | + | in any monad. But this is not true for references - you need to use |

− | readIORef for IO monad, but readSTRef for ST monad, so if you need to | + | readIORef for the IO monad, but readSTRef for the ST monad, so if you need to |

− | implement monad-independent algorithm that uses references, you will | + | implement a monad-independent algorithm that uses references, you will |

be in trouble. This module solves this problem by providing | be in trouble. This module solves this problem by providing | ||

monad-independent operations on boxed and unboxed references. So, the | monad-independent operations on boxed and unboxed references. So, the | ||

following routine: | following routine: | ||

+ | <haskell> | ||

test_Ref = do x <- newRef (0::Int) | test_Ref = do x <- newRef (0::Int) | ||

writeRef x 1 | writeRef x 1 | ||

readRef x | readRef x | ||

+ | </haskell> | ||

− | can be executed | + | can be executed in both the IO and the ST monads: |

− | main = do | + | <haskell> |

− | print | + | main = do a <- test_Ref |

+ | print a | ||

+ | let b = runST test_Ref | ||

+ | print b | ||

+ | </haskell> | ||

− | This example uses the boxed references | + | This example uses the boxed references; unboxed references can be used |

− | in similar way with operations newURef, readURef, writeURef. | + | in a similar way with operations newURef, readURef, writeURef. |

You can find examples of writing monad-independent routines in | You can find examples of writing monad-independent routines in | ||

− | "Examples/Universal.hs". Another | + | "Examples/Universal.hs". Another library of mine, [[Library/Streams]], widely uses this |

facility to implement common functionality for streams working in | facility to implement common functionality for streams working in | ||

different monads. | different monads. | ||

Line 75: | Line 82: | ||

==Syntax sugar for mutable types== | ==Syntax sugar for mutable types== | ||

− | Haskell | + | Haskell doesn't support a convenient syntax for using mutable vars, such |

− | as references, arrays and hash tables. The library includes module | + | as references, arrays and hash tables. The library includes a module |

that partially simplifies their usage. For example: | that partially simplifies their usage. For example: | ||

+ | <haskell> | ||

main = do -- syntax sugar used for reference: | main = do -- syntax sugar used for reference: | ||

x <- ref (0::Int) | x <- ref (0::Int) | ||

x += 1 | x += 1 | ||

x .= (*2) | x .= (*2) | ||

− | val x | + | a <- val x |

+ | print a | ||

+ | |||

-- syntax sugar used for array: | -- syntax sugar used for array: | ||

arr <- newArray (0,9) 0 :: IO Array Int Int | arr <- newArray (0,9) 0 :: IO Array Int Int | ||

(arr,0) =: 1 | (arr,0) =: 1 | ||

− | val (arr,0) > | + | b <- val (arr,0) |

+ | print b | ||

+ | </haskell> | ||

− | Basically, the module supports | + | Basically, the module supports syntactic sugar for using the following |

data types: all types of references, arrays and hash tables. Also, it | data types: all types of references, arrays and hash tables. Also, it | ||

includes two operations to creating references - ref (=newRef) and | includes two operations to creating references - ref (=newRef) and | ||

Line 97: | Line 109: | ||

+= increase | += increase | ||

-= decrease | -= decrease | ||

− | .= apply pure function to contents | + | .= apply a pure function to the contents |

− | .<- apply monadic computation to contents | + | .<- apply a monadic computation to the contents |

val return current value | val return current value | ||

− | + | The left part of these operations can be a reference, array or hash element. Code examples: | |

+ | |||

reference x += 1 | reference x += 1 | ||

(array,index) (arr,0) =: 1 | (array,index) (arr,0) =: 1 | ||

(hash,key) (hash,"str") .= (*2) | (hash,key) (hash,"str") .= (*2) | ||

− | You can also omit extra parentheses when indexing | + | You can also omit extra parentheses when indexing a two- or three-dimensional array: |

(arr,0,1) =: 1 | (arr,0,1) =: 1 | ||

is equivalent to | is equivalent to | ||

(arr,(0,1)) =: 1 | (arr,(0,1)) =: 1 | ||

− | + | Note, that this module supports the array implementations | |

− | included in | + | included in this library, not the standard Data.Array.* modules. Module |

− | "Examples/SyntaxSugar.hs" | + | "Examples/SyntaxSugar.hs" contains further examples. |

Line 119: | Line 132: | ||

==Reimplemented Arrays library== | ==Reimplemented Arrays library== | ||

− | The library also includes modified | + | The library also includes modified implementations of Data.Array.* |

− | modules. The main benefit of these modifications is simplified internal | + | modules. The main benefit of these modifications is a simplified internal |

library structure | library structure | ||

Line 126: | Line 139: | ||

- Unboxed arrays now can be used in polymorphic functions, they are defined | - Unboxed arrays now can be used in polymorphic functions, they are defined | ||

− | for every element type that belongs to classes Unboxed and HasDefaultValue | + | for every element type that belongs to the classes Unboxed and HasDefaultValue |

− | ( | + | (see also [http://www.haskell.org/pipermail/haskell-cafe/2004-July/006400.html]). |

You can add new instances to these classes | You can add new instances to these classes | ||

− | - MArray class now supports arrays with dynamic bounds. It includes | + | - The MArray class now supports arrays with dynamic bounds. It includes |

− | monadic operation getBounds, and if you | + | monadic operation getBounds, and if you change your code to use |

− | this operation with mutable arrays instead of `bounds`, your code also | + | this operation with mutable arrays instead of `bounds`, your code will also |

− | + | be ready to work with dynamic (resizable) arrays | |

− | - Support for dynamic (resizable) arrays included. Their bounds can be | + | - Support for dynamic (resizable) arrays is included. Their bounds can be |

changed either explicitly (by `resizeDynamicArray`) or implicitly (by | changed either explicitly (by `resizeDynamicArray`) or implicitly (by | ||

− | writing to non-existing position). | + | writing to a non-existing position). The policy of automatic array expansion |

− | is selected (or disabled) on array creation. | + | is selected (or disabled) on array creation. |

− | + | ||

− | - Unboxed arrays of Bool values occupy one byte per element (in old | + | - Unboxed arrays of Bool values occupy one byte per element (in the old |

− | implementation they | + | implementation they used one bit per element) |

- castUArray/castIOUArray/castSTUArray operations are non-monadic, | - castUArray/castIOUArray/castSTUArray operations are non-monadic, | ||

− | require "Enum ix" and | + | require "Enum ix" and recalculate upper bounds of arrays according to the |

− | size of elements: UArray (1,2) Word32 -> UArray (1,8) Word8 | + | size of their elements: UArray (1,2) Word32 -> UArray (1,8) Word8 |

− | - Some operations | + | - Some operations may be slower in the new implementation, because I'm |

− | not sure that | + | not sure that I discovered all the clever tricks used in the original library. |

Please test speed and report me about any problems | Please test speed and report me about any problems | ||

− | In other aspects, | + | In other aspects, the new arrays are equivalent to the old ones. |

− | Just change "Array" to | + | Just change "Array" to "ArrayBZ" in your import statements and |

enjoy! :) Directory "Examples/Array" contains demonstrations of using | enjoy! :) Directory "Examples/Array" contains demonstrations of using | ||

each array type | each array type | ||

Line 160: | Line 172: | ||

===Changes in MArray usage=== | ===Changes in MArray usage=== | ||

− | + | The old Arrays library contained the following definitions: | |

+ | <haskell> | ||

class HasBounds a where | class HasBounds a where | ||

bounds :: Ix i => a i e -> (i,i) | bounds :: Ix i => a i e -> (i,i) | ||

− | class (Monad m, HasBounds a) => MArray a e m where ... | + | class (Monad m, HasBounds a) => MArray a e m where |

+ | ... | ||

+ | </haskell> | ||

− | In new library, MArray class defined as: | + | In the new library, the MArray class is defined as: |

+ | <haskell> | ||

class (Monad m) => HasMutableBounds a m where | class (Monad m) => HasMutableBounds a m where | ||

getBounds :: Ix i => a i e -> m (i,i) | getBounds :: Ix i => a i e -> m (i,i) | ||

− | class (Monad m, HasMutableBounds a m) => MArray a e m where ... | + | class (Monad m, HasMutableBounds a m) => MArray a e m where |

+ | ... | ||

+ | </haskell> | ||

− | This means that definitions like this will no | + | This means that definitions like this will no longer work: |

+ | <haskell> | ||

arrayHead :: (MArray a e m, Ix i) => a i e -> m e | arrayHead :: (MArray a e m, Ix i) => a i e -> m e | ||

arrayHead marr = case bounds marr of | arrayHead marr = case bounds marr of | ||

(l,_) -> readArray marr l | (l,_) -> readArray marr l | ||

+ | </haskell> | ||

− | because `bounds` operation is part of HasBounds class that is no | + | because the `bounds` operation is part of HasBounds class, that is no longer a |

− | base class for MArray. | + | base class for MArray. What can you do to fix this problem? Either: |

− | - Add HasBounds restriction to the operation type: | + | - Add a HasBounds restriction to the operation type: |

+ | <haskell> | ||

arrayHead :: (MArray a e m, HasBounds a, Ix i) => a i e -> m e | arrayHead :: (MArray a e m, HasBounds a, Ix i) => a i e -> m e | ||

+ | </haskell> | ||

− | This way, your code will become compatible with both old and new | + | This way, your code will become compatible with both the old and the new |

− | versions of Arrays library, but it will work only with "old" mutable | + | versions of the Arrays library, but it will work only with "old" mutable |

− | arrays and | + | arrays and won't support dynamic arrays. |

− | - Replace | + | - Replace calls to the `bounds` operation with calls to `getBounds`. This |

− | way, your function will become compatible with any instance of MArray | + | way, your function will become compatible with any instance of the MArray |

class, including dynamic arrays: | class, including dynamic arrays: | ||

+ | <haskell> | ||

arrayHead marr = do (l,_) <- getBounds marr | arrayHead marr = do (l,_) <- getBounds marr | ||

readArray marr l | readArray marr l | ||

+ | </haskell> | ||

− | I should mention that despite MArray | + | I should mention that, despite the fact that MArray isn't based on the HasBounds |

− | class, all the old mutable array types (IOArray..StorableArray) still | + | class anymore, all the old mutable array types (IOArray..StorableArray) still |

− | + | implement this interface. Only the new dynamic arrays don't implement | |

it because this is impossible. So, you can use the `bounds` operation | it because this is impossible. So, you can use the `bounds` operation | ||

in code that works with one of "old" array constructors: | in code that works with one of "old" array constructors: | ||

+ | <haskell> | ||

arrayHead :: IOArray i e -> IO e | arrayHead :: IOArray i e -> IO e | ||

arrayHead marr = case bounds marr of | arrayHead marr = case bounds marr of | ||

(l,_) -> readArray marr l | (l,_) -> readArray marr l | ||

+ | </haskell> | ||

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

− | Just to let you know - current implementation of dynamic arrays is | + | Just to let you know - the current implementation of dynamic arrays is |

− | very trivial: it just saves reference (IORef or STRef) to the mutable | + | very trivial: it just saves a reference (IORef or STRef) to the mutable |

− | array. When dynamic array resized, new mutable array is allocated and | + | array. When a dynamic array is resized, a new mutable array is allocated and the |

− | contents copied. New elements are filled with the value | + | 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 dynamic array | + | or newDynamicArray operation. If a dynamic array is created with |

− | newArray_ or newDynamicArray_ | + | newArray_ or newDynamicArray_, then new elements will be left |

undefined. | undefined. | ||

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

+ | <haskell> | ||

resizeDynamicArray array (l,u) | resizeDynamicArray array (l,u) | ||

+ | </haskell> | ||

where (l,u) are new array bounds. If the dynamic array was created | where (l,u) are new array bounds. If the dynamic array was created | ||

− | by newArray or newArray_ operation, it is the only way to resize it - | + | by a newArray or newArray_ operation, it is the only way to resize it - |

− | attempts to write beyond current bounds will raise exception: | + | attempts to write beyond current bounds will raise an exception: |

+ | <haskell> | ||

arr <- newArray (0,-1) 99 :: IO (DynamicIOArray Int Int) | arr <- newArray (0,-1) 99 :: IO (DynamicIOArray Int Int) | ||

resizeDynamicArray arr (0,0) | resizeDynamicArray arr (0,0) | ||

− | writeArray arr 1 1 -- this operation raises | + | writeArray arr 1 1 -- this operation raises an exception |

+ | </haskell> | ||

− | To create array that will be automatically resized on attempt to write | + | To create an array that will be automatically resized on attempt to write |

− | beyond current bounds, you should use newDynamicArray or | + | beyond current bounds, you should use a newDynamicArray or |

− | newDynamicArray_ operation (former | + | newDynamicArray_ operation (the former initializes an array with a given value, |

− | value while | + | 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) | arr <- newDynamicArray_ growTwoTimes (0,-1) :: IO (DynamicIOArray Int Int) | ||

+ | </haskell> | ||

− | This array will grow at least two times each time | + | This array will grow to at least two times its current size, each time automatic |

− | expansion occurs, | + | expansion occurs, which is determined by using the `growTwoTimes` |

− | parameter. This parameter is just | + | parameter. This parameter is just an ordinary function that has the |

following type: | following type: | ||

+ | <haskell> | ||

type GrowBoundsF i = (i,i) -> i -> (i,i) | type GrowBoundsF i = (i,i) -> i -> (i,i) | ||

+ | </haskell> | ||

This function accepts old array bounds and offending index and | This function accepts old array bounds and offending index and | ||

returns new array bounds. You can write new functions for expansion | returns new array bounds. You can write new functions for expansion | ||

− | + | policies yourself, or use one of predefined ones: | |

− | growTwoTimes - expand array at least two times | + | growTwoTimes - expand array to at least two times its current size |

growMinimally - minimal growth that ensures inclusion of new index | growMinimally - minimal growth that ensures inclusion of new index | ||

− | noGrow - disable automatic growth. This policy used for arrays created by newArray or newArray_ | + | noGrow - disable automatic growth. This policy is used for arrays created by newArray or newArray_ |

− | Please note that not every array can work with | + | Please note that not every array can work with every expansion policy |

− | and | + | and that is why I supported freedom of selection of this policy. Only |

− | noGrow policy is compatible with every index type. growMinimally | + | the noGrow policy is compatible with every index type. The growMinimally |

− | policy by | + | policy by its type is compatible with any index, but it will not work |

for partially ordered indexes, in particular for multi-dimensional | for partially ordered indexes, in particular for multi-dimensional | ||

− | arrays. Imagine, for example, array with bounds (0,0)..(9,9). When you | + | 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 new bounds should be (0,0)..(15,9). So you | + | 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, growTwoTimes policy is compatible only with | + | ordered indexes. At last, the growTwoTimes policy is compatible only with |

− | indexes belonging to class Num, but it is most useful policy | + | 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 | + | time expanding arrays. On the other hand, you can provide your own |

− | policy function that will, for example, expand array only 1.5 times. | + | policy function that will, for example, expand an array only 1.5 times. |

− | Dynamic | + | Dynamic arrays support the same MArray and HasMutableBounds interfaces |

− | as other mutable arrays, but they don't support HasBounds interface. | + | as other mutable arrays, but they don't support the HasBounds interface. |

And now about types of dynamic arrays. These types reflect all the | And now about types of dynamic arrays. These types reflect all the | ||

− | types you can use for mutable arrays, and | + | types you can use for mutable arrays, and include DynamicIOArray, |

− | DynamicIOUArray, DynamicSTArray, DynamicSTUArray, | + | DynamicIOUArray, DynamicSTArray, DynamicSTUArray, which have the |

− | same parameters as corresponding arrays without "Dynamic" prefix. | + | same parameters as corresponding arrays without the "Dynamic" prefix. |

Some examples are: | Some examples are: | ||

+ | <haskell> | ||

DynamicIOArray Int Double | DynamicIOArray Int Double | ||

DynamicSTUArray s (Int,Int) Bool | DynamicSTUArray s (Int,Int) Bool | ||

+ | </haskell> | ||

You can also create dynamic arrays from other mutable array types | You can also create dynamic arrays from other mutable array types | ||

− | working in IO monad: | + | working in the IO monad: |

+ | <haskell> | ||

DynamicIO StorableArray Int Double | DynamicIO StorableArray Int Double | ||

+ | </haskell> | ||

− | or ST monad: | + | or the ST monad: |

+ | <haskell> | ||

DynamicST s (STUArray s) (Int,Int) Bool | DynamicST s (STUArray s) (Int,Int) Bool | ||

+ | </haskell> | ||

or any other monad (ask me if you need this). Btw, implementation of | or any other monad (ask me if you need this). Btw, implementation of | ||

dynamic arrays use the monad-independent references class mentioned | dynamic arrays use the monad-independent references class mentioned | ||

above. | above. | ||

+ | |||

+ | |||

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

+ | |||

+ | |||

+ | == Downloading and installation == | ||

+ | |||

+ | You can download the latest version of the library at Hackage, under [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ArrayRef ArrayRef] (0.1 and up), or you can download a version for older GHCs and Hugs, at: | ||

+ | |||

+ | [http://www.haskell.org/library/ArrayRef.tar.gz ArrayRef 0.0] | ||

+ | |||

+ | The library is cabalized. To install it, run command: | ||

+ | |||

+ | make install | ||

+ | |||

+ | Directory "Examples" contains usage examples for the library. | ||

+ | |||

+ | This wiki page is official library documentation. | ||

+ | Please continue to improve it and add more information about using the library. | ||

+ | Feel free to ask me about library usage via email: | ||

+ | [mailto:Bulat.Ziganshin@gmail.com Bulat.Ziganshin@gmail.com] | ||

+ | |||

+ | [[Category:Libraries]] |

## Latest revision as of 19:32, 23 February 2008

The Arrays&References library supports GHC 6.8.x (an older version supports Hugs 2003-2006 and GHC 6.4). It includes the following features:

## Contents |

## [edit] 1 Unboxed references

This substitutes the numerous "fast mutable Ints", "fast mutable Bools" and "fast mutable Ptrs" ghc-specific modules that are used in almost any large project. In contrast to them, this library mimics the well-known interface of IORef/STRef:

import Data.Ref main = do x <- newIOURef (0::Int) writeIOURef x 1 a <- readIOURef x print a

Unboxed references for the IO monad have the type "IOURef a" and operations newIOURef, readIOURef, writeIOURef. Unboxed references for the ST monad have the type "STURef s a" and operations newSTURef, readSTURef, writeSTURef.

Unboxed references can only contain values of the following types: Bool, Char, Int, Int8..Int64, Word, Word8..Word64, Float, Double, Ptr a, FunPtr a, StablePtr a. These types are members of the Unboxed class and you can implement new instances of this class by converting values of some other type (say, CChar) to values of an already supported type.

Despite all these improvements, operations with unboxed references are compiled to the same code as for any "fast mutable variables". Moreover, unboxed references are available even for Hugs, which allows simplified debugging of programs that use them. Please note that unboxed references always hold computed values, in contrast to boxed references, which can contain unevaluated thunks.

I wish to thank Simon Marlow and especially Oleg Kiselyov who proposed the idea of these references and their implementation (in particular, see [1])

You can find examples of using unboxed references in "Examples/URef.hs"

## [edit] 2 Monad-independent references

Sometimes you need to write code that will be compatible with both IO and ST monads, and even better with any monad that is lifted from one of these two. This is especially useful for writing library code that should be as generic as possible. Operations for arrays, for example, are ready for such a kind of usage - readArray and writeArray can work in any monad. But this is not true for references - you need to use readIORef for the IO monad, but readSTRef for the ST monad, so if you need to implement a monad-independent algorithm that uses references, you will be in trouble. This module solves this problem by providing monad-independent operations on boxed and unboxed references. So, the following routine:

test_Ref = do x <- newRef (0::Int) writeRef x 1 readRef x

can be executed in both the IO and the ST monads:

main = do a <- test_Ref print a let b = runST test_Ref print b

This example uses the boxed references; unboxed references can be used in a similar way with operations newURef, readURef, writeURef.

You can find examples of writing monad-independent routines in "Examples/Universal.hs". Another library of mine, Library/Streams, widely uses this facility to implement common functionality for streams working in different monads.

## [edit] 3 Syntax sugar for mutable types

Haskell doesn't support a convenient syntax for using mutable vars, such as references, arrays and hash tables. The library includes a module that partially simplifies their usage. For example:

main = do -- syntax sugar used for reference: x <- ref (0::Int) x += 1 x .= (*2) a <- val x print a -- syntax sugar used for array: arr <- newArray (0,9) 0 :: IO Array Int Int (arr,0) =: 1 b <- val (arr,0) print b

Basically, the module supports syntactic sugar for using the following data types: all types of references, arrays and hash tables. Also, it includes two operations to creating references - ref (=newRef) and uref (=newURef). Other operations include

=: assign += increase -= decrease .= apply a pure function to the contents .<- apply a monadic computation to the contents val return current value

The left part of these operations can be a reference, array or hash element. Code examples:

reference x += 1 (array,index) (arr,0) =: 1 (hash,key) (hash,"str") .= (*2)

You can also omit extra parentheses when indexing a two- or three-dimensional array:

(arr,0,1) =: 1

is equivalent to

(arr,(0,1)) =: 1

Note, that this module supports the array implementations included in this library, not the standard Data.Array.* modules. Module "Examples/SyntaxSugar.hs" contains further examples.

## [edit] 4 Reimplemented Arrays library

The library also includes modified implementations of Data.Array.* modules. The main benefit of these modifications is a simplified internal library structure

Nevertheless, it also includes a few user-visible changes:

- Unboxed arrays now can be used in polymorphic functions, they are defined for every element type that belongs to the classes Unboxed and HasDefaultValue (see also [2]). You can add new instances to these classes

- The MArray class now supports arrays with dynamic bounds. It includes monadic operation getBounds, and if you change your code to use this operation with mutable arrays instead of `bounds`, your code will also be ready to work with dynamic (resizable) arrays

- Support for dynamic (resizable) arrays is included. Their bounds can be changed either explicitly (by `resizeDynamicArray`) or implicitly (by writing to a non-existing position). The policy of automatic array expansion is selected (or disabled) on array creation.

- Unboxed arrays of Bool values occupy one byte per element (in the old implementation they used one bit per element)

- castUArray/castIOUArray/castSTUArray operations are non-monadic, require "Enum ix" and recalculate upper bounds of arrays according to the size of their elements: UArray (1,2) Word32 -> UArray (1,8) Word8

- Some operations may be slower in the new implementation, because I'm not sure that I discovered all the clever tricks used in the original library. Please test speed and report me about any problems

In other aspects, the new arrays are equivalent to the old ones. Just change "Array" to "ArrayBZ" in your import statements and enjoy! :) Directory "Examples/Array" contains demonstrations of using each array type

### [edit] 4.1 Changes in MArray usage

The old Arrays library contained the following definitions:

class HasBounds a where bounds :: Ix i => a i e -> (i,i) class (Monad m, HasBounds a) => MArray a e m where ...

In the new library, the MArray class is defined as:

class (Monad m) => HasMutableBounds a m where getBounds :: Ix i => a i e -> m (i,i) class (Monad m, HasMutableBounds a m) => MArray a e m where ...

This means that definitions like this will no longer work:

arrayHead :: (MArray a e m, Ix i) => a i e -> m e arrayHead marr = case bounds marr of (l,_) -> readArray marr l

because the `bounds` operation is part of HasBounds class, that is no longer a base class for MArray. What can you do to fix this problem? Either:

- Add a HasBounds restriction to the operation type:

arrayHead :: (MArray a e m, HasBounds a, Ix i) => a i e -> m e

This way, your code will become compatible with both the old and the new versions of the Arrays library, but it will work only with "old" mutable arrays and won't support dynamic arrays.

- Replace calls to the `bounds` operation with calls to `getBounds`. This way, your function will become compatible with any instance of the MArray class, including dynamic arrays:

arrayHead marr = do (l,_) <- getBounds marr readArray marr l

I should mention that, despite the fact that MArray isn't based on the HasBounds class anymore, all the old mutable array types (IOArray..StorableArray) still implement this interface. Only the new dynamic arrays don't implement it because this is impossible. So, you can use the `bounds` operation in code that works with one of "old" array constructors:

arrayHead :: IOArray i e -> IO e arrayHead marr = case bounds marr of (l,_) -> readArray marr l

### [edit] 4.2 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:

resizeDynamicArray array (l,u)

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:

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

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:

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

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:

type GrowBoundsF i = (i,i) -> i -> (i,i)

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:

DynamicIOArray Int Double DynamicSTUArray s (Int,Int) Bool

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

DynamicIO StorableArray Int Double

or the ST monad:

DynamicST s (STUArray s) (Int,Int) Bool

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.

## [edit] 5 Downloading and installation

You can download the latest version of the library at Hackage, under ArrayRef (0.1 and up), or you can download a version for older GHCs and Hugs, at:

The library is cabalized. To install it, run command:

make install

Directory "Examples" contains usage examples for the library.

This wiki page is official library documentation. Please continue to improve it and add more information about using the library. Feel free to ask me about library usage via email: Bulat.Ziganshin@gmail.com