This paper was guest-edited by Harry Mairson and Bruce Kapron, for our intended Special Issue on Functional Programming and Computational Complexity. Other papers submitted for the special issue were either out-of-scope or otherwise unsuitable for JFP. Even though only one paper met their high standards, this did not make Harry and Bruce's job any easier, and we thank them for their efforts.

In previous work the author has introduced a lambda calculus SLR with modal and linear types which serves as an extension of Bellantoni–Cook's function algebra BC to higher types. It is a step towards a functional programming language in which all programs run in polynomial time. While this previous work was concerned with the syntactic metatheory of SLR in this paper we develop a semantics of SLR in terms of Chu spaces over a certain category of sheaves from which it follows that all expressible functions are indeed in PTIME. We notice a similarity between the Chu space interpretation and CPS translation which as we hope will have further applications in functional programming.

We present a hierarchical classification of specializations of the divide-and-conquer paradigm. The aim is to identify a subclass of divide-and-conquer algorithms with an efficient parallel implementation which can be viewed as a static space-time mapping. The specializations impose a balanced call tree, a fixed degree of the problem division, and elementwise operations. The correctness of our compile-time transformations is proved by equational reasoning in Haskell; recursion and iteration are handled by induction. We demonstrate the practicality of the skeleton by some examples, one of which is Strassen's matrix multiplication.

To some readers functional pearls may seem like London buses: you can wait ages for one and then two or three come along at once. In the following pages you will find no less than three pearls for your enjoyment and instruction. There are a number of others a little way down the road, so I trust that your pleasure will continue for some time yet.

If my calculations are correct, twenty-seven pearls have been published in the eight and a half years since JFP was inaugurated. There was something of a desert in 1994 and 1995, but since January 1997 they have been appearing in virtually every issue. When I was asked to contribute a regular column to JFP in 1990, the general idea was for something in style that was a mixture of Jon Bentley's Programming Pearls column for the Communications of the ACM, and Martin Rem's Small Programming Exercises section in the Science of Computer Programming. Articles could be on any subject, but they had to be polished, preferably short, and to show something of the unique opportunities a functional perspective could offer to the study of computing. In my own case that usually meant the use of functional notation to derive programs from their specifications, to optimise them, and to reason about their properties in an equational style. Over the years it has emerged that a functional approach is also extremely attractive in the presentation of ideas about data structures, and some very intriguing pearls have been about the use of elegant data structures to achieve efficiency. But there have also been pearls about particular applications, like parsing, pretty-printing, theorem proving, and unification. In fact, practically every area of computing science can benefit from the clarity and brevity a functional approach can offer. That is why I believe the importance of the subject goes beyond the activity of simply writing code in a functional language.

I knew from the outset that I wasn't going to write all of the pearls, and believed that other contributors would soon emerge. Fortunately, I was right: I have written about a third, but some twenty contributors have composed the rest. Authors like writing pearls perhaps because they like responding to the opportunities and challenges provided by the format. All pearls are refereed (including my own), and there is often a fair amount of polishing as a result of the reviewing stage. I would like to record my gratitude to the authors of the pearls so far published (Stephen Adams, Lennart Augustsson, Koen Claessen, Martin Erwig, Jeremy Gibbons, Ralf Hinze, Rob Hoogerwoord, Gerard Huet, Graham Hutton, Patrik Jansson, Johan Jeuring, Andrew Kennedy, Jamie Leifer, Doug Mcllroy, Eric Meijer, Chris Okasaki, Mikael Rittri, Colin Runciman, Bernard Sufrin, Dan Synek) and to ask them, and others, to continue in their good work.

Without adding any primitives to the language, we define a concurrency monad transformer in Haskell. This allows us to add a limited form of concurrency to any existing monad. The atomic actions of the new monad are lifted actions of the underlying monad. Some extra operations, such as fork, to initiate new processes, are provided. We discuss the implementation, and use some examples to illustrate the usefulness of this construction.

Power series and stream processing were made for each other. Stream algorithms for power series are short, sweet, and compositional. Their neatness shines through in Haskell, thanks to pattern-matching, lazy lists, and operator overloading. In a short compass one can build working code from ground zero (scalar operations) up to exact calculation of generating functions and solutions of differential equations.

This paper is about point-free (or ‘pointless’) calculations – calculations performed at the level of function composition instead of that of function application. We address this topic with the help of an example, namely calculating the radix-sort algorithm from a more obvious specification of sorting. The message that we hope to send is that point-free calculations are sometimes surprisingly simpler than the corresponding point-wise calculations.