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 |

**© Simon Thompson, 1998.**

*
Created 15 October 1998.
*