Using compact data representations for languages based on catamorphisms
Leonidas Fegaras · 2018
We describe a new method for improving the performance of functional programs based on catamorphisms. The method relies on using a compact vector representation for the recursive structure over which the catamorphism operates. This saves space and allows catamorphisms to be implemented in tail-recursive fashion even in cases where the standard linked structure representation requires non-tail-recursive evaluation. Preliminary experimental measurements show substantial improvements are possible with our approach. Keywords: program transformation, compilation methods, data representations, catamorphisms. 1 Introduction Most functional languages provide higher-order library functions that capture common computation patterns over recursive data structures. These operators allow algorithms to be expressed at a higher level of abstraction than explicitly recursive programs that manipulate the data structure "one piece at a time." Perhaps the most useful of these operators is the catamorph...