@inproceedings{Bird*99:Program,
  abstract = "It is well-known that each polymorphic function satisfies a certain equational law, called a \emph{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 \emph{higher-order} naturality property. One example is the operation \emph{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.",
  author = "Richard Bird and Jeremy Gibbons and Geraint Jones",
  booktitle = "Millenial Perspectives in Computer Science",
  editor = "J. W. Davies and A. W. Roscoe and J. C. P. Woodcock",
  publisher = "Palgrave",
  title = "Program Optimisation, Naturally",
  url = "http://www.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/naturally.ps.gz",
  year = "2000",
}