| Program Optimisation, Naturally (1999) | |||||||||||||||
Abstract | |||||||||||||||
| It is well-known that each polymorphic function satises a certain equational law, called a naturality condition. Such laws are part and parcel of the basic toolkit for improving the eÆciency 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 eÆciency of some divideand -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. 1 Introduction One of the rst things that any functional programmer learns is how to turn the naive quadratic algorithm for reversing a list into a linear-time algorithm by using an accumulating parameter. In this paper we derive another, quite dierent linear-time algorithm for re... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||