Distilling new data types

Program transformation techniques are commonly used to improve the e ciency of programs. While many transformation techniques aim to remove ine ciencies in the algorithms used in a program, another source of ine ciency is the use of inappropriate datatypes whose structures do not match the algorithmic structure of the program. This mismatch will potentially result in ine cient consumption of the input by the program. Previously, Mogensen has shown how techniques similar to those used in supercompilation can be used to transform datatypes, but this was not fully automatic. In this paper, we present a fully automatic datatype transformation technique which can be applied in conjunction with distillation. The objective of the datatype transformation is to transform the original datatypes in a program so that the resulting structure matches the algorithmic structure of the distilled program. Consequently, the resulting transformed program potentially uses less pattern matching and as a result is more e cient than the original program.