Bridging the algorithm gap: A linear-time functional program for paragraphformatting

In the constructive programming community it is commonplace to see formal d evelopments of textbook algorithms. In the algorithm design community, on t he other hand, it may be well known that the textbook solution to a problem is not the most efficient possible. However, in presenting the more effici ent solution, the algorithm designer will usually omit some of the implemen tation details, thus creating an algorithm gap between the abstract algorit hm and its concrete implementation. This is in contrast to the formal devel opment, which usually proceeds all the way to the complete concrete impleme ntation of the less efficient solution. We claim that the algorithm designe r is forced to omit some of the details by the relative expressive poverty of the Pascal-like languages typically used to present the solution. The gr eater expressiveness provided by a functional language would allow the whol e story to be told in a reasonable amount of space. In this paper we use a functional language to present the development of a sophisticated algorithm all the way to the final code. We hope to bridge the algorithm gap between abstract and concrete implementations, and thereby facilitate communicatio n between the constructive programming and algorithm design communities. (C ) 1999 Elsevier Science B.V. All rights reserved.