[Haskell-cafe] How to use STArray?

[Greg Buchholz]

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...

http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data.Array.Diff.html

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