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