Computer technology changes with frightening speed; the fundamentals, however, remain remarkably static. The architecture of the standard computer is hardly changed from the machines which were built half a century ago, even though their size and power are incomparably different from those of today. In programming, modern ideas like object-orientation have taken decades to move from the research environment into the commercial mainstream. In this light, a functional language like Haskell is a relative youngster, but one with a growing influence to play.

• Functional languages are increasingly being used as components of larger systems like Fran in which Haskell is used to describe reactive graphical animations, which are ultimately rendered in a lower-level language. This inter-operation is done without sacrifice of the semantic elegance which characterises functional languages.
• Functional languages provide a framework in which the crucial ideas of modern programming are presented in the clearest possible way. This accounts for their widespread use in teaching computing science, but also for their influence on the design of other languages. A case in point is the design of G-Java, whose generics are directly modelled on polymorphism in the Haskell mould.

What is functional programming?

Functional programming offers a high-level view of programming, giving its users a variety of features which help them to build elegant yet powerful and general libraries of functions. Central to functional programming is the idea of a function, which computes a result which depends on the values of its inputs.

An example of the power and generality of the language is the map function, which is used to transform every element of a list of objects in a specified way. For example, map can be used to double all the numbers in a sequence of numbers or to invert the colours in each picture from a list of pictures.

The elegance of functional programming is a consequence of the way that functions are defined: an equation is used to say what the value of a function is on an arbitrary input. A simple illustration is the function addDouble which adds two integers and doubles their sum. Its definition is

addDouble x y = 2*(x+y)

The model of functional programming is simple and clean: to work out the value of an expression like

3 + addDouble 4 5

3 + addDouble 4 5
--> 3 + 2*(4+5)
--> ...
--> 21

It is also possible to discuss how the programs behave in general. In the case of addDouble we can use the fact that x+y and y+x are equal for all numbers x and y to conclude that addDouble x y and addDouble y x are equal for all x and y. This idea of proof is much more tractable than those for traditional imperative and object-oriented languages.

Haskell and Hugs

This text uses the programming language Haskell, which has freely-available compilers and interpreters for most types of computer system. Used here is the Hugs interpreter which provides an ideal platform for the learner, with its fast compile cycle, simple interface and free availability for Windows, Unix and Macintosh systems.

Haskell began life in the late 1980s as an intended standard language for lazy functional programming, and since then it has gone through various changes and modifications. This text is written in Haskell 98, which consolidates work on Haskell thus far, and which is intended to be stable; future extensions will result in Haskell 2 some years down the line, but it is expected that implementations will continue to support Haskell 98 after that point.

While the book covers most aspects of Haskell 98, it is primarily a programming text rather than a language manual. Details of the language and its libraries are contained in the language and library reports available from the Haskell home page,

http://www.haskell.org/

Why learn functional programming?

A functional programming language gives a simple model of programming: one value -- the result -- is computed on the basis of others -- the inputs.

Because of its simple foundation, a functional language gives the clearest possible view of the central ideas in modern computing, including abstraction (in a function), data abstraction (in an abstract data type), genericity, polymorphism and overloading. This means that a functional language provides not just an ideal introduction to modern programming ideas, but also a useful perspective on more traditional imperative or object-oriented approaches. For example, Haskell gives a direct implementation of data types like trees, whereas in other languages one is forced to describe them by pointer-linked data structures.

Haskell is not just a good `teaching language'; it is a practical programming language, supported by having extensions such as interfaces to C functions and component-based programming, for example. Haskell has also been used in a number of real-world projects. More information about these extensions and projects can be found in the concluding chapter.

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

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 is needed to use any of the implementations of Haskell. Some logical notation is introduced in the text; this is explained as it appears. In Chapter 19 it would help to have an understanding of the graphs of the log, quadratic and exponential functions.

The approach taken here

There is a tension in writing about a programming language: one wants to introduce all the aspects of the language as early as possible, yet not to over-burden the reader with too much at once. The first edition of the text introduced ideas `from the bottom up', which meant that it took more than a hundred pages before any substantial example could be discussed.

The second edition takes a different approach: a case study of `pictures' introduces a number of crucial ideas informally in the first chapter, revisiting them as the text proceeds. Also, Haskell has a substantial library of built-in functions, particularly over lists, and this edition exploits this, encouraging readers to use these functions before seeing the details of their definitions. This allows readers to progress more quickly, and also accords with practice: most real programs are built using substantial libraries of pre-existing code, and it is therefore valuable experience to work in this way from the start. A section containing details of the other changes in the second edition can be found later in this preface.

Other distictive features of the approach in the book include the following.

• The text gives a thorough treatment of reasoning about functional programs, beginning with reasoning about list-manipulating functions. These are chosen in preference to functions over the natural numbers for two reasons: the results one can prove for lists seem substantially more realistic, and also the structural induction principle for lists seems to be more acceptable to students.
• The Picture case study is introduced in Chapter 1 and revisited throughout the text; this means that readers see different ways of programming the same function, and so get a chance to reflect on and compare different designs.
• Function design -- to be done before starting to code -- is also emphasised explicitly in Chapters 4 and 11.
• There is an emphasis on Haskell as a practical programming language, with an early introduction of modules, as well as a thorough examination of the do notation for I/O and other monad-based applications.
• Types play a prominent role in the text. Every function or object defined has its type introduced at the same time as its definition. Not only does this provide a check that the definition has the type that its author intended, but also we view types as the single most important piece of documentation for a definition, since a function's type describes precisely how the function is to be used.
• A number of case studies are introduced in stages through the book: the picture example noted above, an interactive calculator program, a coding and decoding system based on Huffman codes and a small queue simulation package. These are used to introduce various new ideas and also to show how existing techniques work together.
• Support materials on Haskell, including a substantial number of Web links, are included in the concluding chapter. Various appendices contain other backup information including details of the availability of implementations, common Hugs errors and a comparison between functional, imperative and OO programming.
• Other support materials appear on the Web site for the book
  http://www.cs.kent.ac.uk/people/staff/sjt/craft2e/

Outline

The introduction in Chapter 1 covers the basic concepts of functional programming: functions and types, expressions and evaluation, definitions and proof. Some of the more advanced ideas, such as higher-order functions and polymorphism are previewed here from the perspective of the example of pictures built from characters. The second chapter looks at the practicalities of the Hugs implementation of Haskell, loading and running scripts written in traditional and `literate' styles, and the basics of the module system. It also contains a first exercise using the Picture type. These two chapters together cover the foundation on which to build a course on functional programming in Haskell.

Information on how to build simple programs over numbers, characters and Booleans is contained in Chapter 3. The basic lessons are backed up with exercises, as is the case for all chapters from here on. With this basis, Chapter 4 steps back and examines the various strategies which can be used to define functions, and particularly emphasises the importance of using other functions, either from the system or written by the user, and also the idea of `divide and conquer', as well as introducing recursion over the natural numbers.

Structured data, in the form of tuples and lists, come in Chapter 5. After introducing the idea of lists, programming over lists is performed using two resources: the list comprehension, which effectively gives the power of map and filter; and the first-order prelude and library functions. Nearly all the list prelude functions are polymorphic, and so polymorphism is brought in here. Chapter 6 contains various extended examples, and only in Chapter 7 is primitive recursion over lists introduced; a text processing case study provides a more substantial example here.

Chapter 8 introduces reasoning about list-manipulating programs, on the basis of a number of introductory sections giving the appropriate logical background. Guiding principles about how to build inductive proofs are presented, together with a more advanced section on building successful proofs from failed attempts.

Higher-order functions are introduced in Chapters 9 and 10. First functional arguments are examined, and it is shown that functional arguments allow the implementation of many of the `patterns' of computation identified over lists at the start of the chapter. Chapter 10 covers functions as results, defined both as lambda-expressions and as partial applications; these ideas are examined by revisiting the Picture example, as well as through an index case study. This is followed by an interlude -- Chapter 11 -- which discusses the role of the development life cycle in programming.

Type classes allow functions to be overloaded to mean different things at different types; Chapter 12 covers this topic as well as surveying the various classes built into Haskell. The Haskell type system is somewhat complicated because of the presence of classes, and so Chapter 13 explores the way in which types are checked in Haskell. In general type checking is a matter of resolving the various constraints put upon the possible type of the function by its definition.

In writing larger programs, it is imperative that users can define types for themselves. Haskell supports this in two ways. Algebraic types like trees are the subject of Chapter 14, which covers all aspects of algebraic types from design and proof to their interaction with type classes, as well as introducing numerous examples of algebraic types in practice. These examples are consolidated in Chapter 15 which contains the case study of coding and decoding of information using a Huffman-style code. The foundations of the approach are outlined before the implementation of the case study. Modules are used to break the design into manageable parts, and the more advanced features of the Haskell module system are introduced at this point.

An abstract data type (ADT) provides access to an implementation through a restricted set of functions. Chapter 16 explores the ADT mechanism of Haskell and gives numerous examples of how it is used to implement queues, sets, relations and so forth, as well as giving the basics of a simulation case study.

Chapter 17 introduces lazy evaluation in Haskell which allows programmers a distinctive style incorporating backtracking and also infinite data structures. As an example of backtracking there is a parsing case study, and infinite lists are used to give `process style' programs as well as a random-number generator.

Haskell programs can perform input and output by means of the IO types. Their members -- examined in Chapter 18 -- represent action-based programs. The programs are most readily written using the do notation, which is introduced at the start of the chapter, and illustrated through a series of examples, culminating in an interactive front-end to the calculator. The foundations of the do notation lie in monads which can also be used to do action-based programming of a number of different flavours, some of which are examined in the second half of the chapter.

The text continues with an examination in Chapter 19 of program behaviour, by which we mean the time taken for a program to compute its result, and the space used in that calculation. Chapter 20 concludes by surveying various applications and extensions of Haskell as well as looking at further directions for study. These are backed up with Web and other references.

The appendices cover various background topics. The first examines links with functional and OO programing, and the second gives a glossary of commonly used terms in functional programming. The others include a summary of Haskell operators and Hugs errors, together with help on understanding programs and details of the various implementations of Haskell.

The Haskell code for all the examples in the book, as well as other background materials can be downloaded from the Web site for the book.

What has changed from the first edition?

`Bottom up' or not?

Most importantly, the philosophy of how to introduce material has changed, and this makes most impact on how lists are handled. The first edition was written with a resolutely `bottom up' approach, first introducing recursive definitions of monomorphic functions, and only later bringing in the built-in functions of the prelude and the libraries. This edition starts by introducing in Chapter 5 the (first-order) polymorphic list-manipulating functions from the prelude as well as list comprehensions, and only introduces recursive definitions over lists in Chapter 7.

The main reason for this change was the author's (and others') experience that once recursion had been introduced early, it was difficult to get students to move on and use other sorts of definitions, in particular it was difficult to get students to use prelude and library functions in their solutions. This is bad in itself, and gives students only a partial view of the language. Moreover, it rests ill with modern ideas about programming which emphasise the importance of re-use and putting together solutions which make use of a rich programming environment which provides many of the required building blocks.

Introduction

Another consequence of the first-edition approach that it took some hundred pages before any substantial examples could be introduced; in this edition there is an example of pictures in Chapter 1 which both forms a more substantial case study and is used to preview the ideas of polymorphism, higher-order functions and type abstraction in Chapter 1. The case study is revisited repeatedly as new material is brought in, showing how the same problems can be solved more effectively with new machinery, as well as illustrating the idea of program verification.

The introduction also sets out more clearly some of the basic concepts of functional programming and Haskell, and a separate Chapter 2 is used to discuss the Hugs systems, Haskell scripts and modules and so forth.

Haskell 98

The book now has an emphasis on using the full resources of Haskell 98. Hugs now provides an almost complete implementation of Haskell, and so as far as systems are concerned Hugs is the exclusive subject. In most situations Hugs will probably be the implementation of choice for teaching purposes, and if it is not used, it is only the system descriptions which need to be ignored, as none of the language features described are Hugs-specific.

The treatment of abstract data types use the Haskell mechanism exclusively, rather than the restricted type synonym mechanism of Hugs which was emphasised in the first edition. The material on I/O now starts with the do notation, treating it as a mini language for describing programs with actions. This is followed by a general introduction to monads, giving an example of monadic computation over trees which again uses the do notation.

Finally, functions in the text are given the same names as they have in the prelude or libraries, which was not always the case in the first edition. Type variables are the customary a, b, ... and list variables are named xs, ys and so on.

Recursion, types and proof

As hinted earlier, recursion is given less emphasis than before.

The material on type checking now takes the approach of looking more explictily at the constraints put upon types by definitions, and empasises this through a sequence of examples. This replaces an approach which stated typing rules but said less about their application in practice.

Students have made the point that proof over lists seems more realistic and indeed easier to understand than proof over the natural numbers. For that reason, proof over lists is introduced in Chapter 8 rather than earlier. This has the advantage that practical examples can be brought in right from the start, and the material on proof is linked with the pictures case study.

Problem solving and patterns of definition

Because of a concern for `getting students started' in solving problems, there is an attempt to talk more explictly about strategies for programming, reorganising and introducing new material in Chapters 4 and 11; this material owes much to Polya's problem solving approach in mathematics. There is also explicit discussion about various `patterns of definition' of programs in Section 9.1.

Conclusion and appendices

The new edition contains a concluding chapter which looks to further resources, both printed and on the Web, as well as discussing possible directions for functional programming.

Some material from the appendices has been incorporated into the conclusion, whilst the appendix discussing links with other paradigms says rather more about links with OO ideas. The other appendices have been updated, and that on `some useful functions' has been absorbed into the body of the text.

To the reader

This introduction to functional programming in Haskell is designed to be read from start to finish, but some material can be omitted, or read in a different order.

The material is presented in an order that the author finds natural, and whilst this also reflects some of the logical dependencies between parts of the subject, some material later in the text can be read earlier than it appears. Specifically, the introductions to I/O in the first four sections of Chapter 18 and to algebraic types in the early sections on Chapter 14 can be tackled at any point after reading Chapter 7.

It is always an option is to cover only a subset of the topics, and this can be achieved by stopping before the end; the rest of this section discusses in more detail other ways of trimming the material.

There is a thread on program verification which begins with Chapter 8 and continues in Sections 10.9, 14.7, 16.10 and 17.9; this thread is optional. Similarly, Chapter 19 gives a self-contained treatment of program time and space behaviour which is also optional.

Some material is more technical, and can be omitted on (at least the) first reading. This is signalled explicitly in the text, and is contained in Sections 8.7 and part of Section 13.2.

Finally, it is possible to omit some of the examples, and case studies. For example, Sections 6.2 and 6.4 are extended sets of exercises which need not be covered; the text processing (Section 7.6) and indexing (Section 10.8) can also be omitted -- their roles are to provide reinforcement and to show the system used on rather larger examples. In the later chapters, the examples in Sections 14.6 and 16.7-16.9 and in Chapter 17 can be skipped, but paring too many examples will run the risk of losing some motivating material.

Chapter 15 introduces modules in the first two sections; the remainder is the Huffman coding case study, which is optional. Finally, distributed through the final chapters are the calculator and simulation case studies. These are again optional, but omission of the calculator case study will remove an important illustration of parsing and algebraic and abstract data types.

Acknowledgements

Emma Mitchell and Michael Strang of Addison-Wesley have supported this second edition from its inception; thanks very much to them.

Particular thanks to Jane for devotion beyond the call of duty in reading and commenting very helpfully on the first two chapters, as well as for her support over the last months while I have been writing this edition. Finally, thanks to Alice and Rory who have more than readliy shared our home PC with Haskell.

Simon Thompson
Canterbury, October 1998

© Simon Thompson, 1998.

Created 15 October 1998.