The material is presented in three parts.

Part I: Basic functional programming

The aim of Part I is to introduce the basic tools of functional programming, and to give detailed guidance about how to build programs to solve particular problems.

The technical material covers the basic types of Miranda: numbers, characters and Booleans, and the structured types of tuples and lists. Readers are introduced to function definitions involving guards, pattern matching and local definitions
(where clauses) through a sequence of examples and sections.

Throughout the introduction, details are given about how particular problems can be approached, to encourage students to develop their own solutions. Divide and conquer approaches, and top-down design are encouraged, and illustrated by means of examples including a small database, the production of supermarket bills, text processing and equation solving.

To animate the programs, calculations of many examples are given, and readers are encouraged to try definitions out using these rewriting sequences. Integrated into this and the other Parts of the book are proofs of program properties. These are shown to be written to a template, in the cases of proof over numbers and lists, and many examples of graded difficulty are presented. More traditional approaches to software testing are also discussed and encouraged.

The material in this Part is all first-order and non-polymorphic, deliberately. The aim of the Part is to give students a firm grounding on which they can make the abstractions which are the subject of the next Part.

Part II: Abstraction

This Part forms the bridge between the material on basic functional programming, and the larger-scale programs of the final Part. The distinctive features of languages like Miranda are that they are higher-order, allowing functions as arguments to and results of other functions, and polymorphic with definitions applying to, for instance, all types of list rather than to lists of a single type.

Higher-order and polymorphic functions are shown in this Part to be generalizations or abstractions of definitions familiar from the first Part: an example is the map function which applies an operation to every member of a list, irrespective of the operation (it is a parameter) and the type of the list.

These technical ideas are introduced, and many of the examples of Part I are re-examined to show the general higher-order functions they exemplify or use. Libraries of general functions are developed, particularly over the polymorphic list type.

The consequences of these ideas for software design and engineering are also examined: polymorphic higher-order functions are ideal candidates for re-use, and this is illustrated in the examples.

The most technical Chapter of the book is the final one of this Part, where type checking is presented. This is necessary fully to exploit the features of the language, and also to understand the error messages which result when type checking fails.

Program verification is a continuing theme here, and it is argued that theorems about general functions are re-usable in the same way as the functions themselves.

Part III: Larger-scale programming

The final Part of the book brings in the aspects of the language which support larger-scale programming: user defined concrete (or algebraic) types; modules; abstract data types. In introducing each of these, examples are given, together with general principles for design of systems which contain algebraic and abstract data types, as well as how systems are built top-down and bottom-up using modules.

Amongst the examples we look at are the design and use of Huffman codes, the simulation of multiple queues (as might be found in a bank), finding the difference between two files, simple interactive programs and aspects of a simple arithmetic calculator.

Lazy evaluation is also discussed here. After showing precisely what it means and how it works, the consequences it has for program development are explored. These include data-directed solutions, infinite data structures and interactive streams of input and output. Design principles for interactive programs are explored, and verification is addressed.

The book concludes with an analysis of program behaviour, including the time taken and spaced used during evaluation. Examples from the text are re-visited, and various strategies for optimising program performance are introduced.

Appendices, Bibliography and Index

The appendices consist of: a comparison of functional and imperative programming; a glossary of commonly used and technical terms; sources for further reading; a discussion of common error messages, and their possible sources; an annotated listing of some of the built-in functions (the standard environment) and a reminder of the ways that unfamiliar definitions can be understood.

Next Up