Haskell
The Craft of Functional Programming
Second Edition

Chapter 1 Introducing functional programming	1
1.1 Computers and modelling	1
1.2 What is a function?	3
1.3 Pictures and functions	4
1.4 Types	5
1.5 The Haskell programming language	6
1.6 Expressions and evaluation	6
1.7 Definitions	8
1.8 Function definitions	9
1.9 Looking forward: a model of pictures	12
1.10 Proof	14
1.11 Types and functional programming	16
1.12 Calculation and evaluation	16
Chapter 2 Getting started with Haskell and Hugs	19
2.1 A first Haskell program	19
2.2 Using Hugs	22
2.3 The standard prelude and the Haskell libraries	26
2.4 Modules	26
2.5 A second example: `Pictures`	27
2.6 Errors and error messages	30
Chapter 3 Basic types and definitions	33
3.1 The Booleans: `Bool`	33
3.2 The Integers: `Int`	36
3.3 Overloading	38
3.4 Guards	38
3.5 The characters: `Char`	42
3.6 Floating point numbers: `Float`	43
3.7 Syntax	47
Chapter 4 Designing and writing programs	53
4.1 Where do I start? Designing a program in Haskell	53
4.2 Recursion	58
4.3 Primitive recursion in practice	61
4.4 General forms of recursion	64
4.5 Program testing	66
Chapter 5 Data types: tuples and lists	71
5.1 Introducing tuples, lists and strings	71
5.2 Tuple types	73
5.3 Our approach to lists	76
5.4 Lists in Haskell	77
5.5 List comprehensions	79
5.6 A library database	82
5.7 Generic functions: polymorphism	86
5.8 Haskell list functions in `Prelude.hs`	89
5.9 The `String` type	91
Chapter 6 Programming with lists	97
6.1 The `Picture` example, revisited.	97
6.2 Extended exercise: positioned pictures	101
6.3 Local definitions	104
6.4 Extended exercise: supermarket billing	109
Chapter 7 Defining functions over lists	115
7.1 Pattern matching revisited	115
7.2 Lists and list patterns	116
7.3 Primitive recursion over lists	119
7.4 Finding primitive recursive definitions	120
7.5 General recursions over lists	125
7.6 Example: Text Processing	128
Chapter 8 Reasoning about programs	135
8.1 Understanding definitions	135
8.2 Testing and proof	137
8.3 Definedness, termination and finiteness	138
8.4 A little logic	139
8.5 Induction	140
8.6 Further examples of proofs by induction	144
8.7 Generalizing the proof goal	147
Chapter 9 Generalization: patterns of computation	151
9.1 Patterns of computation over lists	152
9.2 Higher-order functions: functions as arguments	154
9.3 Folding and primitive recursion	159
9.4 Generalizing: splitting up lists	163
Chapter 10 Functions as values	167
10.1 Function-level definitions	167
10.2 Function composition	168
10.3 Functions as values and results	171
10.4 Partial Application	175
10.5 Revisiting the `Picture` example	180
10.6 Further examples	183
10.7 Currying and uncurrying	184
10.8 Example: creating an index	186
10.9 Verification and general functions	192
Chapter 11 Program development	203
11.1 The development cycle	203
11.2 Development in practice	204
Chapter 12 Overloading and type classes	211
12.1 Why overloading?	211
12.2 Introducing classes	212
12.3 Signatures and Instances	215
12.4 A tour of the built-in Haskell classes	220
12.5 Types and Classes	226
Chapter 13 Checking types	229
13.1 Monomorphic type checking	230
13.2 Polymorphic type checking	232
13.3 Type checking and classes	240
Chapter 14 Algebraic types	243
14.1 Introducing algebraic types	244
14.2 Recursive algebraic types	250
14.3 Polymorphic algebraic types	258
14.4 Case study: Program Errors	261
14.5 Design with Algebraic Data Types	265
14.6 Algebraic types and type classes	269
14.7 Reasoning about algebraic types	275
Chapter 15 Case study: Huffman codes	281
15.1 Modules in Haskell	281
15.2 Modular design	285
15.3 Coding and decoding	286
15.4 Implementation -- I	288
15.5 Building Huffman trees	291
15.6 Design	292
15.7 Implementation -- II	292
Chapter 16 Abstract data types	301
16.1 Type representations	301
16.2 The Haskell abstract data type mechanism	303
16.3 Queues	306
16.4 Design	309
16.5 Simulation	311
16.6 Implementing the simulation	313
16.7 Search trees	317
16.8 Sets	322
16.9 Relations and graphs	328
16.10 Commentary	336
Chapter 17 Lazy programming	339
17.1 Lazy evaluation	340
17.2 Calculation rules and lazy evaluation	342
17.3 List comprehensions revisited	345
17.4 Data-directed programming	352
17.5 Case study: Parsing expressions	356
17.6 Infinite lists	366
17.7 Why infinite lists?	372
17.8 Case study: Simulation	375
17.9 Proof revisited	377
Chapter 18 Programming with actions	385
18.1 Why is I/O an issue?	386
18.2 The basics of input/output	387
18.3 The `do` notation	389
18.4 Iteration and recursion	393
18.5 The calculator	397
18.6 Further I/O	400
18.7 The `do` construct revisited	401
18.8 Monads for Functional Programming	403
18.9 Example: Monadic computation over trees	408
Chapter 19 Time and space behaviour	415
19.1 Complexity of functions	415
19.2 The complexity of calculations	419
19.3 Implementations of sets	423
19.4 Space behaviour	424
19.5 Folding revisited	427
19.6 Avoiding re-computation: memoization	431
Chapter 20 Conclusion	437
Appendix A Functional, imperative and OO programming	443
Appendix B Glossary	451
Appendix C Haskell operators	459
Appendix D Understanding programs	461
Appendix E Implementations of Haskell	465
Appendix F Hugs errors	467
Bibliography
Index

Created 15 October 1998.

Haskell The Craft of Functional Programming Second Edition

Contents

Haskell
The Craft of Functional Programming
Second Edition