|
Data.Array.Diff | Portability | non-portable | Stability | experimental | Maintainer | libraries@haskell.org |
|
|
|
|
Contents |
- Diff array types
- Overloaded immutable array interface
- Low-level interface
|
|
Description |
Functional arrays with constant-time update.
|
|
Synopsis |
|
|
|
|
Diff array types |
|
Diff arrays have an immutable interface, but rely on internal
updates in place to provide fast functional update operator
//. When the // operator is applied to a diff array, its contents
are physically updated in place. The old array silently changes
its representation without changing the visible behavior:
it stores a link to the new current array along with the
difference to be applied to get the old contents. So if a diff array is used in a single-threaded style,
i.e. after // application the old version is no longer used,
a'!'i takes O(1) time and a // d takes O(length d).
Accessing elements of older versions gradually becomes slower. Updating an array which is not current makes a physical copy.
The resulting array is unlinked from the old family. So you
can obtain a version which is guaranteed to be current and
thus have fast element access by a // []. |
|
data IOToDiffArray a i e |
An arbitrary MArray type living in the IO monad can be converted
to a diff array. | Instances | |
|
|
Type synonyms for the two most important IO array types. |
|
type DiffArray = IOToDiffArray IOArray |
Fully polymorphic lazy boxed diff array. |
|
type DiffUArray = IOToDiffArray IOUArray |
Strict unboxed diff array, working only for elements
of primitive types but more compact and usually faster than DiffArray. |
|
Overloaded immutable array interface |
|
Module Data.Array.IArray provides the interface of diff arrays.
They are instances of class IArray. |
|
module Data.Array.IArray |
|
Low-level interface |
|
These are really internal functions, but you will need them
to make further IArray instances of various diff array types
(for either more MArray types or more unboxed element types). |
|
newDiffArray :: (MArray a e IO, Ix i) => (i, i) -> [(Int, e)] -> IO (IOToDiffArray a i e) |
|
readDiffArray :: (MArray a e IO, Ix i) => IOToDiffArray a i e -> Int -> IO e |
|
replaceDiffArray :: (MArray a e IO, Ix i) => IOToDiffArray a i e -> [(Int, e)] -> IO (IOToDiffArray a i e) |
|
Produced by Haddock version 0.4 |