Haskell
The Craft of Functional Programming

Preface

Over the last fifteen years, functional programming has come of age. It has been used successfully on a number of substantial projects. A variety of robust and efficient implementations of functional languages have been developed. A functional language is taught as the first programming language in many university computing courses, and at a later stage in most others. Before examining the reasons for its popularity, we give a short overview of functional programming.

What is functional programming?

Functional programming is based on the simplest of models, namely that of finding the value of an expression. This we meet in our first years at school, when we learn to work out expressions like 8+(3-2) by evaluating the two halves, 8 and (3-2), and adding the results together. Functional programming consists of our defining for ourselves functions like + which we can then use to form expressions.

We define these functions by means of equations, like

addD a b = 2*(a+b)                                    (1)

which we use to calculate the value of an expression like addD 2 (addD 3 4). We evaluate this using (1) to replace applications of addD with their values, so that we can write down a calculation of the value of the expression thus:

addD 2 (addD 3 4)
= 2*(2 + (addD 3 4))
= 2*(2 + 2*(3 + 4))
= 32

As well as using (1) to calculate, we can read it as a logical description of how the function addD behaves on any values a and b; on the basis of this we can reason about how it behaves. For instance, for any values a and b,

addD a b = 2*(a+b) = 2*(b+a) = addD b a

This equation holds for all possible input values, in contrast to the information we gain from testing a function at a selection of inputs.

On top of this simple model we can build a variety of facilities, which give the functional approach its distinctive flavour. These include higher-order functions, whose arguments and results are themselves functions; polymorphism, which allows a single definition to apply simultaneously to a collection of types; and infinite data structures which are used to model a variety of data objects.

The Haskell language also has support for larger-scale programming, including user-defined algebraic types, such as lists, trees and so on; abstract data types; type classes and modules. These contribute to separating complex tasks into smaller sub-tasks, making the components of systems independent of each other, as well as supporting software re-use.

Why learn functional programming?

As a vehicle for learning programming principles a functional language like Haskell has many advantages. As we have seen, it is based on a simple model which allows us both to perform evaluation by hand, animating our understanding, and to reason about how the programs behave. In this text, both calculation and reasoning have a central part.

The language is higher-level than most. For example, in Haskell the type of lists is defined directly as a recursive type, and so there is no need to examine its implementation by pointers; indeed the functional language can be used as a design language for an imperative implementation. A second instance is provided by polymorphism; generic definitions are introduced with almost no overhead, in contrast to object-oriented languages such as Modula-3 and C++. Haskell also allows, through its type classes, overloading of names to mean similar things at different types. Moreover, the language supports larger-scale programming by means of its abstract data type and module mechanisms.

For these reasons we see Haskell as providing a sound introduction to programming principles, which can be complemented later by learning an imperative language. Equally valuable is to learn Haskell after using a more traditional language, since it can broaden our view of the programming process as well as illustrating many software engineering techniques of general worth.

Haskell, Hugs and Gofer

The Haskell programming language is set out in the Haskell 1.3 language definition, and the programs in this book conform to that definition. (This is with the exception of abstract data types which use the approach found in Gofer and Hugs. However, a full explanation of the Haskell mechanism is also provided.) Haskell 1.3 is broadly similar to version 1.2; the most notable changes lie in the input/output mechanism, and the way in which libraries are organised.

The finalisation of the Haskell 1.3 definition has been going on during the final editing of the book, and changes in the definition have been tracked to the best of the author's ability. As the definition is in advance of available implementations, the code available for the programs in the text will be available in Haskell 1.2 and 1.3 forms, for Gofer, Hugs and other implementations of the standard. The pertinent differences are documented in the code, which can be obtained as described below.

Haskell is an advanced programming language, intended for real-world applications, and so it contains a multitude of features. In this introductory text we cannot hope to cover the whole language, although we do aim to include brief descriptions of some of the features we omit, as well as pointers to the literature.

Beginning students of a language benefit from using as simple an implementation as possible. For this reason we describe the Hugs and Gofer interpreters as we go. Gofer is a Haskell-like language, whose major difference from Haskell is in its type class mechanism, whereas Hugs (for Haskell Users' Gofer System) is an implementation of Haskell, apart from the fact that the current release does not implement the module system. The Haskell programs we give also work in Gofer, with the exception of some of the more advanced class-based functions. We have also implemented the programs containing modules using the Glasgow Haskell compiler; for details of this and other implementations of Haskell see the Appendices.

The approach

The material is grouped into three parts. In the first, we build a foundation, focusing on programming over basic types and lists, using first-order, non-polymorphic programs. Only when readers are fluent with the basics of functions, types and program construction do we look at the three ideas of higher-order functions, polymorphism and type classes, which together give modern functional programming its distinctive flavour and power. Based on this, in the final part we look at larger-scale programming, supported also by an exploration of user-defined types, modules, input/output and lazy evaluation, and concluding with an analysis of program efficiency.

As we saw at the beginning of the preface, we can write down calculations of expressions which use our defined functions, and also give proofs of various of their properties; both aspects are emphasised in the text, although it can be read independently of the material on proof.

The crucial test of any programming text is whether it helps the reader to write programs. The book is called `The Craft of Functional Programming' because it aims to give readers help with design of programs right from the start. At each stage we give advice on how functions, types or modules can be designed; in many cases we give a series of steps which aim to simplify the problem by breaking it down into smaller parts.

Software of any importance will be modified during its lifetime; modification and re-use are emphasised when we discuss design, and in the final part of the book we look in particular at how libraries of polymorphic higher-order functions can be re-used in many different contexts.

The advice on design is supplemented by examples and case studies of varying size and complexity. Some, like the Huffman coding example, are free-standing; others, such as the library database, are re-visited a number of times to illustrate how new techniques can be applied to solve existing problems in different ways. This is important in linking together the different parts of the text, and in showing the variety of ways that any problem can be solved in Haskell.

Finally, other case studies are introduced step-by-step. We first see the simulation example when we design algebraic data types in Chapter 10; next it provides realistic examples of abstract data types in Chapter 12, and finally we look at its top level in Chapter 13. Each aspect is separate; together they provide a substantial case study. Other aspects of our approach are

Throughout the text, whenever a function is defined we give its type explicitly; the type forms the first and most important piece of documentation for any definition.
Material is included on how to find proofs by induction; a template to help with setting down the precise goals of an induction proof is included, as is a discussion of how to search for proofs about functions defined by equations.
Appendices contain support material of various kinds. In one we give pointers to sites from which implementations of Haskell and Gofer can be obtained. Common errors and error messages are collected in a second; a glossary of programming terms commonly used in another. A fourth appendix gives functions from parts of the Haskell standard preludes, a fifth examines how functional and imperative programming are linked and a sixth gives references for further reading. Finally, we give an overview of how to understand an unfamiliar function definition in Haskell.
Over four hundred exercises of varying difficulty are included.
Further support material, including the code for all the definitions in the text and support material for teachers, can be found on the World Wide Web page
```
http://www.ukc.ac.uk/computer_science/Haskell_craft/
```

Outline

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 Haskell: numbers, both integers and floating-point, characters and Booleans, and the structured types of tuples and lists. Readers are introduced to function definitions involving guards, pattern matching and local definitions 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 methods and top-down design are encouraged, and illustrated by means of examples including a small database, the production of supermarket bills, text processing and the solution of various sorts of algebraic equation.

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. The approach in this part of the book is purposely slow and intended to reinforce ideas through examples; we indicate which sections may be omitted to make a `fast track' in the notes for the teacher below.

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 Haskell are that they are higher-order, allowing functions as arguments to and results of other functions; they are polymorphic, with definitions applying to, for instance, all types of list rather than to lists of a single type; and finally they contain classes, which give a mechanism for overloading names to mean similar things at different types. Classes also support an object-oriented style which we touch on in Part III.

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 (which becomes a parameter) and the type of the list.

The simplest example of an overloaded function is equality, ==, which uses different methods at different types to check the equality of two elements. We say that types with an equality function belong to the equality class Eq, and in general a type belongs to a class if the functions in the class definition are defined over that particular type.

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 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.

For more complex interactions we show how a monadic approach to I/O is useful, and we also introduce an example of a monadic program in a general programming setting. 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 from the standard preludes and a reminder of the ways that unfamiliar definitions can be understood. We also give pointers to sites from which implementations of Haskell can be obtained.

Who should read this book?

This text is intended as an introduction to functional programming for computer science and other students, principally at university level. It can be used by beginners to computer science, or more experienced students who are learning functional programming for the first time; either group will find the material is new, challenging and interesting.

The book can also be used for self-study by programmers, software engineers and others interested in gaining a grounding in functional programming.

The text is intended to be self-contained, but some elementary knowledge of commands, files and so on would be needed to use any of the implementations of Haskell. Some logical notation is introduced in the text; this is explained as it appears. In the final chapter it would be helpful to have an understanding of the graphs of the log, polynomial and exponential functions.

To the teacher

Depending upon a teacher's preferences and the context in which the course is taught, different routes through the book exist. The ordering of the text roughly corresponds to the first year course at the University of Kent, although the material here is much expanded from that given to our students.

The book follows a linear progression, and it makes sense to follow it from Chapter 1 to Chapter 15; if time does not permit, a coherent course on smaller-scale programming is given by the first part; together with the second, students will gain an additional grounding in the novelties of functional programming, whilst more advanced techniques are introduced in Part III. For a `fast track' through Part I, one can omit Sections 2.9, 2.13, the exercise in 2.14, 4.7, 4.8 and 5.4.

In Part III it is possible to pick and choose chapters and sections, rather than following the material page-by-page. The case studies illustrate the material, but a teacher could use his or her own examples rather than those of Huffman coding or relations and graphs, for instance. The calculator and simulation examples are distributed through Part III; another approach would be to delay them until all the supporting material has been studied.

Integral to this course is reasoning about programs, but the material on proof in this text stands independently, and so a proof-free course could be given by omitting Chapters 3 and 5, and Sections 7.8, 10.7 and 13.9. It would also be feasible to give the proof material rather later than it appears in the text. Also standing alone is the material on program behaviour; this could be omitted if so desired.

It is impossible to exclude some more technical sections from the book, but some of this material could be deferred, mentioned in passing or given an informal gloss. In the first two parts, Sections 5.4, 8.4 and 9.3 are potential candidates.

Students should be encouraged to use the information in the appendices. Depending upon their backgrounds, the comparison of functional and imperative programming can be illuminating in both directions; at the University of Kent we find that linking the treatment of lists in a functional and an imperative language is very helpful for students who are learning the intricacies of pointer-based linked lists

Also to be recommended to students is the glossary; both for beginners to programming, and to those familiar with other programming paradigms, some of the terminology of functional programming is either new or consists of common terms used in a slightly different way from the norm. In either case, students should be encouraged to look up words they are unsure about. Also in the appendices are a full treatment of common errors, a reminder of the different ways to understand an unfamiliar function and sources for further reading.

Resources for teachers, including the program text for all the definitions in the book (in both Haskell and Gofer) and a teachers' guide are available on-line from the World Wide Web page mentioned above.

Acknowledgements

I am very grateful indeed to Roy Dyckhoff and Ham Richards, whose refereeing of the manuscript has brought to light numerous errors and slips of the finger. Equally importantly, they have been able to suggest many ways of improving the presentation of the ideas in the book. Olaf Chitil, Steve Hill, Tom Locke and Dan Russell have performed a similar service for the material on type classes and monads.

I have used Hugs and Gofer in writing the text, and I therefore very much appreciate the efforts of Mark Jones in building these excellent systems. Many of the programs here were translated into Haskell; this was made much easier by the mira2hs program written by Denis Howe.

The staff at Addison-Wesley have smoothed the way of the book at every stage. Particular thanks are due to Simon Plumtree, Stephen Bishop and Dylan Reisenberger for editing and production in the UK, as well as Ari Davidow in the USA for World Wide Web support and CRB Associates for typesetting. At the University of Kent, Sally Fincher, Louise Heery and Richard Hesketh have endured my novice's questions about the Web with great good humour.

Jane, Alice and Rory have again come up trumps, making space and providing support while I was writing the book; thank you all very much.

Simon Thompson
Canterbury, April 1996

Haskell The Craft of Functional Programming