How to automatically translate pure code into code that uses mutable arrays for efficiency?

This is a Haskell question, but I'd also be interested in answers about other languages. Is there a way to automatically translate purely functional code, written to process either lists or immutable arrays without doing any destructive updates, into code that uses mutable arrays for efficiency?

In Haskell the generated code would either run in the ST monad (in which case it would all be wrapped in runST or runSTArray) or in the IO monad, I assume.

I'm most interested in general solutions which work f开发者_如何学运维or any element type.

I thought I've seen this before, but I can't remember where. If it doesn't already exist, I'd be interested in creating it.

---

Implementing a functional language using destructive updates is a memory management optimization. If an old value will no longer be used, it is safe to reuse the old memory to hold a new values. Detecting that a value will not be used anymore is a difficult problem, which is why reuse is still managed manually.

Linear type inference and uniqueness type inference discover some useful information. These analyses discover variables that hold the only reference to some object. After the last use of that variable, either the object is transferred somewhere else, or the object can be reused to hold a new value.

Several languages, including Sisal and SAC, attempt to reuse old array memory to hold new arrays. In SAC, programs are first converted to use explicit memory management (specifically, reference counting) and then the memory management code is optimized.

---

You say "either lists or immutable arrays", but those are actually two very different things, and in many cases algorithms naturally suited to lists would be no faster (and possibly slower) when used with mutable arrays.

For instance, consider an algorithm consisting of three parts: Constructing a list from some input, transforming the list by combining adjacent elements, then filtering the list by some criterion. A naive approach of fully generating a new list at each step would indeed be inefficient; a mutable array updated in place at each step would be an improvement. But better still is to observe that only a limited number of elements are needed simultaneously and that the linear nature of the algorithm matches the linear structure of a list, which means that all three steps can be merged together and the intermediate lists eliminated entirely. If the initial input used to construct the list and the filtered result are significantly smaller than the intermediate list, you'll save a lot of overhead by avoiding extra allocation, instead of filling a mutable array with elements that are just going to be filtered out later anyway.

Mutable arrays are most likely to be useful when making a lot of piecemeal, random-access updates to an array, with no obvious linear structure. When using Haskell's immutable arrays, in many cases this can be expressed using the accum function in Data.Array, which I believe is already implemented using ST.

In short, a lot of the simple cases either have better optimizations available or are already handled.

Edit: I notice this answer was downvoted without comment and I'm curious why. Feedback is appreciated, I'd like to know if I said something dumb.