Diff arrays have immutable interface (Section 4.17), 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 // [].
An arbitrary MArray type living in the IO monad can be converted to a diff array with the type constructor IOToDiffArray. It has kind (* -> * -> *) -> * -> * -> *, where parameters mean the following:
internal mutable array type constructor, which is itself parametrized over index and element types
index type
element type
Two most important diff array types are fully polymorphic lazy boxed DiffArray = IOToDiffArray IOArray, and strict unboxed DiffUArray = IOToDiffArray IOUArray, working only for elements of primitive types, but more compact and usually faster. These type constructors should be applied to the index type and element type, providing an array type which is an instance of IArray.