Editing Arrays (section)

=== Welcome to the machine: Array#, MutableArray#, ByteArray#, MutableByteArray#, pinned and moveable byte arrays ===

The GHC heap contains two kinds of objects. Some are just byte sequences,
while the others are pointers to other objects (so-called "boxes"). This
segregation allows the system to find chains of references when performing
garbage collection and to update these pointers when memory used by the heap
is compacted and objects are moved to new places. The internal (raw) GHC
type Array# represents a sequence of object pointers (boxes). There is a
low-level operation in the ST monad which allocates an array of specified size in the heap.
Its type is something like (Int -> ST s Array#). The Array# type is used
inside the Array type which represents boxed immutable arrays.

There is a different type for '''mutable''' boxed arrays
(IOArray/STArray), namely MutableArray#. A separate type for mutable
arrays is required because of the 2-stage garbage collection mechanism.
The internal representations of Array# and MutableArray# are the same
apart from some flags in header, and this make possible to perform in-place
convsion between MutableArray# and Array# (this is that
unsafeFreeze and unsafeThaw operations do).

Unboxed arrays are represented by the ByteArray# type. This is just a plain
memory area in the Haskell heap, like a C array. There are two primitive operations
that create a ByteArray# of specified size. One allocates memory in the
normal heap and so this byte array can be moved when
garbage collection occurs. This prevents the conversion of a ByteArray#
to a plain memory pointer that can be used in C procedures (although
it's still possible to pass a current ByteArray# pointer to an "'''unsafe'''
foreign" procedure if the latter doesn't try to store this pointer somewhere).
The second primitive allocates a ByteArray# of a specified size in the
"pinned" heap area, which contains objects with a fixed location. Such a byte
array will never be moved by garbage collection, so its address can be used as a plain
Ptr and shared with the C world. The first way to create ByteArray# is used
inside the implementation of all UArray types, while the second way is used in
StorableArray (although StorableArray can also point to data
allocated by C malloc). Pinned ByteArray# also used in ByteString.

There is also a MutableByteArray# type which is very similar to ByteArray#, but GHC's primitives support only monadic read/write
operations for MutableByteArray#, and only pure reads for ByteArray#,
as well as the unsafeFreeze/unsafeThaw operations which change appropriate
fields in headers of this arrays. This differentiation doesn't make much
sense except for additional safety checks.

So, pinned MutableByteArray# or C malloced memory is used inside
StorableArray, pinned ByteArray# or C malloced memory - inside
ByteString, unpinned MutableByteArray# - inside IOUArray and
STUArray, and unpinned ByteArray# is used inside UArray.

The API's of boxed and unboxed arrays API are almost identical:

 marr <- alloc n            - allocates a mutable array of the given size
 arr  <- unsafeFreeze marr  - converts a mutable array to an immutable one
 marr <- unsafeThaw arr     - converts an immutable array to a mutable one
 x    <- unsafeRead marr i  - monadic reading of the value with the given index from a mutable array
 unsafeWrite marr i x       - monadic writing of the value with the given index from a mutable array
 let x = unsafeAt arr i     - pure reading of the value with the given index from an immutable array
 (all indices are counted from 0)

Based on these primitive operations, the array library implements
indexing with any type and with any lower bound, bounds checking and
all other high-level operations. Operations that create
immutable arrays just create them as mutable arrays in the ST monad, make
all required updates on this array, and then use unsafeFreeze before
returning the array from runST. Operations on IO arrays are implemented
via operations on ST arrays using the stToIO operation.