Program Optimisation‚ Naturally
Richard Bird‚ Jeremy Gibbons and Geraint Jones
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.
Details
| Book Title |
Millenial Perspectives in Computer Science |
| Editor |
J. W. Davies and A. W. Roscoe and J. C. P. Woodcock |
| Publisher |
Palgrave |
| Year |
2000 |
Links
Related pages
|
People |
|
|
Activities |