# Contents

Chapter 1 Introducing functional programming1
1.1 Computers and modelling1
1.2 What is a function?3
1.3 Pictures and functions4
1.4 Types5
1.5 The Haskell programming language6
1.6 Expressions and evaluation6
1.7 Definitions8
1.8 Function definitions9
1.9 Looking forward: a model of pictures12
1.10 Proof14
1.11 Types and functional programming16
1.12 Calculation and evaluation16
Chapter 2 Getting started with Haskell and Hugs19
2.1 A first Haskell program19
2.2 Using Hugs22
2.3 The standard prelude and the Haskell libraries26
2.4 Modules26
2.5 A second example: `Pictures`27
2.6 Errors and error messages30
Chapter 3 Basic types and definitions33
3.1 The Booleans: `Bool`33
3.2 The Integers: `Int`36
3.4 Guards38
3.5 The characters: `Char`42
3.6 Floating point numbers: `Float`43
3.7 Syntax47
Chapter 4 Designing and writing programs53
4.1 Where do I start? Designing a program in Haskell53
4.2 Recursion58
4.3 Primitive recursion in practice61
4.4 General forms of recursion64
4.5 Program testing66
Chapter 5 Data types: tuples and lists71
5.1 Introducing tuples, lists and strings71
5.2 Tuple types73
5.3 Our approach to lists76
5.4 Lists in Haskell77
5.5 List comprehensions79
5.6 A library database82
5.7 Generic functions: polymorphism86
5.8 Haskell list functions in `Prelude.hs`89
5.9 The `String` type91
Chapter 6 Programming with lists97
6.1 The `Picture` example, revisited.97
6.2 Extended exercise: positioned pictures101
6.3 Local definitions104
6.4 Extended exercise: supermarket billing109
Chapter 7 Defining functions over lists115
7.1 Pattern matching revisited115
7.2 Lists and list patterns116
7.3 Primitive recursion over lists119
7.4 Finding primitive recursive definitions120
7.5 General recursions over lists125
7.6 Example: Text Processing128
Chapter 8 Reasoning about programs135
8.1 Understanding definitions135
8.2 Testing and proof137
8.3 Definedness, termination and finiteness138
8.4 A little logic139
8.5 Induction140
8.6 Further examples of proofs by induction144
8.7 Generalizing the proof goal147
Chapter 9 Generalization: patterns of computation151
9.1 Patterns of computation over lists152
9.2 Higher-order functions: functions as arguments154
9.3 Folding and primitive recursion159
9.4 Generalizing: splitting up lists163
Chapter 10 Functions as values167
10.1 Function-level definitions167
10.2 Function composition168
10.3 Functions as values and results171
10.4 Partial Application175
10.5 Revisiting the `Picture` example180
10.6 Further examples183
10.7 Currying and uncurrying184
10.8 Example: creating an index186
10.9 Verification and general functions192
Chapter 11 Program development203
11.1 The development cycle203
11.2 Development in practice204
12.2 Introducing classes212
12.3 Signatures and Instances215
12.4 A tour of the built-in Haskell classes220
12.5 Types and Classes226
Chapter 13 Checking types229
13.1 Monomorphic type checking230
13.2 Polymorphic type checking232
13.3 Type checking and classes240
Chapter 14 Algebraic types243
14.1 Introducing algebraic types244
14.2 Recursive algebraic types250
14.3 Polymorphic algebraic types258
14.4 Case study: Program Errors261
14.5 Design with Algebraic Data Types265
14.6 Algebraic types and type classes269
14.7 Reasoning about algebraic types275
Chapter 15 Case study: Huffman codes281
15.1 Modules in Haskell281
15.2 Modular design285
15.3 Coding and decoding286
15.4 Implementation -- I288
15.5 Building Huffman trees291
15.6 Design292
15.7 Implementation -- II292
Chapter 16 Abstract data types301
16.1 Type representations301
16.2 The Haskell abstract data type mechanism303
16.3 Queues306
16.4 Design309
16.5 Simulation311
16.6 Implementing the simulation313
16.7 Search trees317
16.8 Sets322
16.9 Relations and graphs328
16.10 Commentary336
Chapter 17 Lazy programming339
17.1 Lazy evaluation340
17.2 Calculation rules and lazy evaluation342
17.3 List comprehensions revisited345
17.4 Data-directed programming352
17.5 Case study: Parsing expressions356
17.6 Infinite lists366
17.7 Why infinite lists?372
17.8 Case study: Simulation375
17.9 Proof revisited377
Chapter 18 Programming with actions385
18.1 Why is I/O an issue?386
18.2 The basics of input/output387
18.3 The `do` notation389
18.4 Iteration and recursion393
18.5 The calculator397
18.6 Further I/O400
18.7 The `do` construct revisited401
18.8 Monads for Functional Programming403
18.9 Example: Monadic computation over trees408
Chapter 19 Time and space behaviour415
19.1 Complexity of functions415
19.2 The complexity of calculations419
19.3 Implementations of sets423
19.4 Space behaviour424
19.5 Folding revisited427
19.6 Avoiding re-computation: memoization431
Chapter 20 Conclusion437
Appendix A Functional, imperative and OO programming443
Appendix B Glossary451
Appendix C Haskell operators459
Appendix D Understanding programs461
Appendix E Implementations of Haskell465
Appendix F Hugs errors467
Bibliography
Index

© Simon Thompson, 1998.

Created 15 October 1998.