[Haskell-cafe] How to use STArray?

Greg Buchholz haskell at sleepingsquirrel.org
Thu Aug 25 11:58:35 EDT 2005

Bayley, Alistair wrote:
> I have a pure function which uses immutable arrays from Data.Array, but it
> spends about 95% of its time doing array updates. The arrays are used in a
> single-threaded manner (no need for the old values after an array update),

    This is probably completely off-topic, but you might also be
interested in looking at diff arrays...


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. 

Greg Buchholz

More information about the Haskell-Cafe mailing list