Mutable boxed and unboxed arrays in the ST monad.

Software Transactional Memory: a modular composable concurrency abstraction. See
* *Composable memory transactions*, by Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy, in /ACM Conference on Principles and Practice of Parallel Programming/ 2005. http://research.microsoft.com/Users/simonpj/papers/stm/index.htm

Software Transactional Memory: a modular composable concurrency abstraction. See
* *Composable memory transactions*, by Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy, in /ACM Conference on Principles and Practice of Parallel Programming/ 2005. http://research.microsoft.com/Users/simonpj/papers/stm/index.htm
This module only defines the STM monad; you probably want to import Control.Concurrent.STM (which exports Control.Monad.STM).

Mutable, boxed, non-strict arrays in the ST monad. The type arguments are as follows:
* s: the state variable argument for the ST type
* i: the index type of the array (should be an instance of Ix)
* e: the element type of the array.

A monad supporting atomic memory transactions.

A monad transformer version of the ST monad Warning! This monad transformer should not be used with monads that can contain multiple answers, like the list monad. The reason is that the will be duplicated across the different answers and this cause Bad Things to happen (such as loss of referential transparency). Safe monads include the monads State, Reader, Writer, Maybe and combinations of their corresponding monad transformers.
Version 0.3.1

A mutable array with unboxed elements, that can be manipulated in the ST monad. The type arguments are as follows:
* s: the state variable argument for the ST type
* i: the index type of the array (should be an instance of Ix)
* e: the element type of the array. Only certain element types are supported.
An STUArray will generally be more efficient (in terms of both time and space) than the equivalent boxed version (STArray) with the same element type. However, STUArray is strict in its elements - so don't use STUArray if you require the non-strictness that STArray provides.

Strict RWS monad.
Inspired by the paper *Functional Programming with Overloading and Higher-Order Polymorphism*, Mark P Jones (http://web.cecs.pdx.edu/~mpj/) Advanced School of Functional Programming, 1995.

State monads.
This module is inspired by the paper *Functional Programming with Overloading and Higher-Order Polymorphism*, Mark P Jones (http://web.cecs.pdx.edu/~mpj/) Advanced School of Functional Programming, 1995.

Strict state monads.
This module is inspired by the paper *Functional Programming with Overloading and Higher-Order Polymorphism*, Mark P Jones (http://web.cecs.pdx.edu/~mpj/) Advanced School of Functional Programming, 1995.

A monad transformer that combines ReaderT, WriterT and StateT. This version is strict; for a lazy version, see Control.Monad.Trans.RWS.Lazy, which has the same interface.

State monads, passing an updatable state through a computation.
Some computations may not require the full power of state transformers:
* For a read-only state, see Control.Monad.Trans.Reader.
* To accumulate a value without using it on the way, see Control.Monad.Trans.Writer.
This version is lazy; for a strict version, see Control.Monad.Trans.State.Strict, which has the same interface.

Strict state monads, passing an updatable state through a computation. See below for examples.
In this version, sequencing of computations is strict. For a lazy version, see Control.Monad.Trans.State.Lazy, which has the same interface.
Some computations may not require the full power of state transformers:
* For a read-only state, see Control.Monad.Trans.Reader.
* To accumulate a value without using it on the way, see Control.Monad.Trans.Writer.

The strict WriterT monad transformer, which adds collection of outputs (such as a count or string output) to a given monad.
This version builds its output strictly; for a lazy version, see Control.Monad.Trans.Writer.Lazy, which has the same interface.
This monad transformer provides only limited access to the output during the computation. For more general access, use Control.Monad.Trans.State instead.

Strict writer monads.
Inspired by the paper *Functional Programming with Overloading and Higher-Order Polymorphism*, Mark P Jones (http://web.cecs.pdx.edu/~mpj/pubs/springschool.html) Advanced School of Functional Programming, 1995.

Parallel Evaluation Strategies, or Strategies for short, provide ways to express parallel computations. Strategies have the following key features:
* Strategies express *deterministic parallelism*: the result of the program is unaffected by evaluating in parallel. The parallel tasks evaluated by a Strategy may have no side effects. For non-deterministic parallel programming, see Control.Concurrent.
* Strategies let you separate the description of the parallelism from the logic of your program, enabling modular parallelism. The basic idea is to build a lazy data structure representing the computation, and then write a Strategy that describes how to traverse the data structure and evaluate components of it sequentially or in parallel.
* Strategies are *compositional*: larger strategies can be built by gluing together smaller ones.
* Monad and Applicative instances are provided, for quickly building strategies that involve traversing structures in a regular way.
For API history and changes in this release, see Control.Parallel.Strategies#history.

A storable array is an IO-mutable array which stores its contents in a contiguous memory block living in the C heap. Elements are stored according to the class Storable. You can obtain the pointer to the array contents to manipulate elements from languages like C.
It is similar to IOUArray but slower. Its advantage is that it's compatible with C.

An efficient implementation of maps from integer keys to values (dictionaries).
API of this module is strict in both the keys and the values. If you need value-lazy maps, use Data.IntMap.Lazy instead. The IntMap type itself is shared between the lazy and strict modules, meaning that the same IntMap value can be passed to functions in both modules (although that is rarely needed).
These modules are intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.
> import Data.IntMap.Strict (IntMap)
> import qualified Data.IntMap.Strict as IntMap
The implementation is based on *big-endian patricia trees*. This data structure performs especially well on binary operations like union and intersection. However, my benchmarks show that it is also (much) faster on insertions and deletions when compared to a generic size-balanced map implementation (see Data.Map).
* Chris Okasaki and Andy Gill, "*Fast Mergeable Integer Maps*", Workshop on ML, September 1998, pages 77-86, http://citeseer.ist.psu.edu/okasaki98fast.html
* D.R. Morrison, "/PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric/", Journal of the ACM, 15(4), October 1968, pages 514-534.
Operation comments contain the operation time complexity in the Big-O notation http://en.wikipedia.org/wiki/Big_O_notation. Many operations have a worst-case complexity of *O(min(n,W))*. This means that the operation can become linear in the number of elements with a maximum of *W* -- the number of bits in an Int (32 or 64).
Be aware that the Functor, Traversable and Data instances are the same as for the Data.IntMap.Lazy module, so if they are used on strict maps, the resulting maps will be lazy.

An efficient implementation of ordered maps from keys to values (dictionaries).
API of this module is strict in both the keys and the values. If you need value-lazy maps, use Data.Map.Lazy instead. The Map type is shared between the lazy and strict modules, meaning that the same Map value can be passed to functions in both modules (although that is rarely needed).
These modules are intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.
> import qualified Data.Map.Strict as Map
The implementation of Map is based on *size balanced* binary trees (or trees of *bounded balance*) as described by:
* Stephen Adams, "*Efficient sets: a balancing act*", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB/.
* J. Nievergelt and E.M. Reingold, "*Binary search trees of bounded balance*", SIAM journal of computing 2(1), March 1973.
Note that the implementation is *left-biased* -- the elements of a first argument are always preferred to the second, for example in union or insert.
Operation comments contain the operation time complexity in the Big-O notation (http://en.wikipedia.org/wiki/Big_O_notation).
Be aware that the Functor, Traversable and Data instances are the same as for the Data.Map.Lazy module, so if they are used on strict maps, the resulting maps will be lazy.