Program Optimisation‚ Naturally

Abstract

It is well-known that each polymorphic function satisfies a certain equational law, called a naturality condition. Such laws are part and parcel of the basic toolkit for improving the efficiency of functional programs. More rarely, some polymorphic functions also possess a higher-order naturality property. One example is the operation unzip that takes lists of pairs to pairs of lists. Surprisingly, this property can be invoked to improve the asymptotic efficiency of some divide-and-conquer algorithms from O(n log n) to O(n). The improved algorithms make use of polymorphic recursion, and can be expressed neatly using nested datatypes, so they also serve as evidence of the practical utility of these two concepts.