Transformational programming and the paragraph problem
The problem of breaking paragraphs into lines can be formulated as an optimisation problem: the best arrangement of lines is one which minimises a certain definition of waste. Starting with a specification of this kind, we present a complete derivation, based on transformational programming, of two linear-time algorithms for the problem. The difference between the algorithms reflects different assumptions about the algebraic properties of waste functions: one algorithm employs a greedy strategy, while the other uses dynamic programming. Both algorithms are expressed as purely functional programs, and the advantages of a functional notation are illustrated in the derivations.
- Bridging the algorithm gap: A linear-time functional program for paragraph formatting
- scientific article; zbMATH DE number 910715
- Transformational program development in a particular problem domain
- AI 2003: Advances in Artificial Intelligence
- Transformational programming and the derivation of algorithms
- From algebra to operational semantics
- See more through lenses than bananas
- Bridging the algorithm gap: A linear-time functional program for paragraph formatting
- List partitions
- Polynomial-time optimal pretty-printing combinators with choice
- Categories, relations and dynamic programming
- AI 2003: Advances in Artificial Intelligence
- Efficient memo-table management strategies
- Mapping a functional notation for parallel programs onto hypercubes
- An exercise in transformational programming: Backtracking and Branch-and- Bound
This page was built for publication: Transformational programming and the paragraph problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1067769)
