Recycle Your Arrays!
In PADL'09: 11th International Symposium on Practical Aspects of Declarative Languages, pp. 209-223, Springer-Verlag, 2009
Download: PDF
Purely functional arrays are notoriously difficult to implement and use efficiently due to the absence of destructive updates and the resultant frequent copying. Deforestation frameworks such as stream fusion achieve signficant improvements here but fail for a number of important operations which can nevertheless benefit from elimination of temporaries. To mitigate this problem, we extend stream fusion with support for in-place execution of array operations. This optimisation, which we call recycling, is easy to implement and can significantly reduce array allocation and copying in purely functional array algorithms.
Array recycling is implemented in the vector package.