Data.Array.Diff

Functional arrays with constant-time update.

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

IArray (IOToDiffArray IOUArray) Bool

IArray (IOToDiffArray IOUArray) Char

IArray (IOToDiffArray IOUArray) Double

IArray (IOToDiffArray IOUArray) Float

IArray (IOToDiffArray IOUArray) Int

IArray (IOToDiffArray IOUArray) Int8

IArray (IOToDiffArray IOUArray) Int16

IArray (IOToDiffArray IOUArray) Int32

IArray (IOToDiffArray IOUArray) Int64

IArray (IOToDiffArray IOUArray) Word

IArray (IOToDiffArray IOUArray) Word8

IArray (IOToDiffArray IOUArray) Word16

IArray (IOToDiffArray IOUArray) Word32

IArray (IOToDiffArray IOUArray) Word64

IArray (IOToDiffArray IOArray) e

IArray (IOToDiffArray IOUArray) (StablePtr a)

IArray (IOToDiffArray IOUArray) (Ptr a)

IArray (IOToDiffArray IOUArray) (FunPtr a)

(Ix ix, Show ix) => Show (DiffUArray ix Word64)

(Ix ix, Show ix) => Show (DiffUArray ix Word32)

(Ix ix, Show ix) => Show (DiffUArray ix Word16)

(Ix ix, Show ix) => Show (DiffUArray ix Word8)

(Ix ix, Show ix) => Show (DiffUArray ix Int64)

(Ix ix, Show ix) => Show (DiffUArray ix Int32)

(Ix ix, Show ix) => Show (DiffUArray ix Int16)

(Ix ix, Show ix) => Show (DiffUArray ix Int8)

(Ix ix, Show ix) => Show (DiffUArray ix Double)

(Ix ix, Show ix) => Show (DiffUArray ix Float)

(Ix ix, Show ix) => Show (DiffUArray ix Word)

(Ix ix, Show ix) => Show (DiffUArray ix Int)

(Ix ix, Show ix) => Show (DiffUArray ix Char)

(Ix ix, Show ix) => Show (DiffUArray ix Bool)

(Ix ix, Show ix, Show e) => Show (DiffArray ix e)

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)