Haskell
The Craft of Functional Programming

Table of Contents


Part I Basic Functional Programming

Chapter 1 Introducing functional programming

1.1 What is Functional Programming?
1.2 Haskell
1.3 Gofer and Hugs
1.4 Practical work

Chapter 2 Basic types and simple programs

2.1 The numbers: Integers
2.2 Programming with integers
2.3 Syntax
2.4 Operators
2.5 Definitions: Patterns
2.6 Programming with Booleans
2.7 Characters and Strings
2.8 Floating point numbers
2.9 Programming with numbers and strings
2.10 Data structures: Tuples
2.11 Function Definitions
2.12 Programming with local definitions
2.13 Example: Quadratic equations
2.14 Design

Chapter 3 Reasoning about programs

3.1 Informal proof: an introduction
3.2 Proof by Induction
3.3 Building induction proofs

Chapter 4 Data structures: Lists

4.1 Lists in Haskell
4.2 Defining functions over lists
4.3 Designing functions over lists
4.4 Pattern matching
4.5 A library database
4.6 List comprehensions
4.7 Extended exercise: supermarket billing
4.8 Example: Text Processing
4.9 Definition forms
4.10 Program design

Chapter 5 Reasoning about lists

5.1 Structural induction
5.2 Proofs by structural induction
5.3 Case studies
5.4 Generalizing the proof goal

Part II Abstraction

Chapter 6 Generalization

6.1 Functions as arguments
6.2 Polymorphism
6.3 Putting the two together
6.4 Using the higher-order functions
6.5 Generalizing: splitting up lists

Chapter 7 Functions as values

7.1 Function composition
7.2 Functions as values and results
7.3 Partial Application
7.4 Examples
7.5 Currying and uncurrying
7.6 Example: creating an index
7.7 Design revisited
7.8 Verification

Chapter 8 Classes in Haskell

8.1 Introducing classes
8.2 Signatures and Instances
8.3 A tour of the built-in Haskell classes
8.4 More advanced features

Chapter 9 Checking Types

9.1 Monomorphic types
9.2 Polymorphic types
9.3 Polymorphic Type Checking
9.4 Type checking & classes

Part III Larger-scale programming

Chapter 10 Algebraic types

10.1 Introduction
10.2 Recursive Types
10.3 Polymorphic algebraic types
10.4 Case study: Program Errors
10.5 Design with Algebraic Data Types
10.6 Algebraic types and type classes
10.7 Reasoning about algebraic types

Chapter 11 Case study: Huffman codes

11.1 Modules in Haskell
11.2 Modular design
11.3 Coding and decoding
11.4 Implementation -- I
11.5 Building Huffman trees
11.6 Design
11.7 Implementation -- II

Chapter 12 Abstract data types

12.1 Type representations
12.2 The Gofer abstract data type mechanism
12.3 Example: queues
12.4 The Haskell ADT mechanism
12.5 Design
12.6 Example: Simulation
12.7 Implementing the simulation
12.8 Example: Search trees
12.9 Case Study: Sets
12.10 Relations and graphs
12.11 Commentary

Chapter 13 Lazy programming

13.1 Lazy evaluation
13.2 Calculation Rules
13.3 List comprehensions revisited
13.4 Data on demand
13.5 Case study: Parsing expressions
13.6 Infinite lists
13.7 Why infinite lists?
13.8 Case study: Simulation
13.9 Proof revisited

Chapter 14 Input/Output and Interaction

14.1 Stream-based interactive programs
14.2 Using Monads for I/O
14.3 Monads for Functional Programming

Chapter 15 Program behaviour

15.1 Complexity of functions
15.2 The complexity of calculations
15.3 Implementations of sets
15.4 Space behaviour
15.5 Folding revisited
15.6 Avoiding re-computation: memoization

Appendices

A Functional and imperative programming
B Further reading
C Glossary
D Understanding programs
E Haskell operators
F Implementations of Haskell
G Gofer and Hugs errors
H Some Useful Functions

Bibliography
Index


© Simon Thompson, 1996.

Last modified 5 May 1996.