Haskell: The Craft of Functional Programming (International Computer Science Series)

One of the leading textbooks on Haskell programming, this third edition is thoroughly revised throughout and includes new material on testing and domain-specific languages and a variety of new examples and case studies, including simple games. Cover......Page 1 Contents......Page 8 Preface......Page 14 Chapter 1: Introducing functional programming......Page 24 1.1 Computers and modelling......Page 25 1.2 What is a function?......Page 26 1.3 Pictures and functions......Page 27 1.4 Types......Page 28 1.5 The Haskell programming language......Page 30 1.6 Expressions and evaluation......Page 31 1.7 Definitions......Page 32 1.8 Function definitions......Page 34 1.9 Types and functional programming......Page 37 1.10 Calculation and evaluation......Page 38 1.11 The essence of Haskell programming......Page 39 1.12 Domain-specific languages......Page 40 1.13 Two models of Pictures......Page 41 1.14 Tests, properties and proofs......Page 45 Summary......Page 48 2.1 A first Haskell program......Page 50 2.2 Using Haskell in practice......Page 51 2.3 Using GHCi......Page 52 2.4 The standard prelude and the Haskell libraries......Page 56 2.5 Modules......Page 57 2.6 A second example: pictures......Page 58 2.7 Errors and error messages......Page 61 Summary......Page 63 Chapter 3: Basic types and definitions......Page 64 3.1 The Booleans: Bool......Page 65 3.2 The integers: Integer and Int......Page 68 3.4 Guards......Page 71 3.5 Characters and strings......Page 75 3.6 Floating-point numbers: Float......Page 79 3.7 Syntax......Page 83 Summary......Page 89 4.1 Where do I start? Designing a program in Haskell......Page 90 4.2 Solving a problem in steps: local definitions......Page 95 4.3 Defining types for ourselves: enumerated types......Page 101 4.4 Recursion......Page 104 4.5 Primitive recursion in practice......Page 107 4.6 Extended exercise: pictures......Page 110 4.7 General forms of recursion......Page 112 4.8 Program testing......Page 114 Summary......Page 118 5.1 Introducing tuples and lists......Page 120 5.2 Tuple types......Page 123 5.3 Introducing algebraic types......Page 126 5.5 Lists in Haskell......Page 132 5.6 List comprehensions......Page 134 5.7 A library database......Page 139 Summary......Page 144 6.1 Generic functions: polymorphism......Page 146 6.2 Haskell list functions in the Prelude......Page 149 6.3 Finding your way around the Haskell libraries......Page 152 6.4 The Picture example: implementation......Page 158 6.5 Extended exercise: alternative implementations of pictures......Page 163 6.6 Extended exercise: positioned pictures......Page 167 6.7 Extended exercise: supermarket billing......Page 170 Summary......Page 177 7.1 Pattern matching revisited......Page 178 7.2 Lists and list patterns......Page 180 7.3 Primitive recursion over lists......Page 183 7.4 Finding primitive recursive definitions......Page 184 7.5 General recursions over lists......Page 190 7.6 Example: text processing......Page 193 Summary......Page 198 8.1 Rock – Paper – Scissors: strategies......Page 200 8.2 Why is I/O an issue?......Page 204 8.3 The basics of input/output......Page 205 8.4 The do notation......Page 208 8.5 Loops and recursion......Page 212 8.6 Rock – Paper – Scissors: playing the game......Page 214 Summary......Page 217 Chapter 9: Reasoning about programs......Page 218 9.1 Understanding definitions......Page 219 9.2 Testing and proof......Page 220 9.3 Definedness, termination and finiteness......Page 222 9.4 A little logic......Page 223 9.5 Induction......Page 224 9.6 Further examples of proofs by induction......Page 228 9.7 Generalizing the proof goal......Page 232 Summary......Page 235 Chapter 10: Generalization: patterns of computation......Page 236 10.1 Patterns of computation over lists......Page 237 10.2 Higher-order functions: functions as arguments......Page 239 10.3 Folding and primitive recursion......Page 244 10.4 Generalizing: splitting up lists......Page 249 10.5 Case studies revisited......Page 250 Summary......Page 252 Chapter 11: Higher-order functions......Page 254 11.1 Operators: function composition and application......Page 255 11.2 Expressions for functions: lambda abstractions......Page 258 11.3 Partial application......Page 262 11.4 Under the hood: curried functions......Page 265 11.5 Defining higher-order functions......Page 270 11.6 Verification and general functions......Page 276 Summary......Page 285 12.1 Revisiting the Picture example......Page 286 12.2 Functions as data: strategy combinators......Page 289 12.3 Functions as data: recognizing regular expressions......Page 292 12.4 Case studies: functions as data......Page 295 12.5 Example: creating an index......Page 298 12.6 Development in practice......Page 304 12.7 Understanding programs......Page 307 Summary......Page 309 13.1 Why overloading?......Page 310 13.2 Introducing classes......Page 311 13.3 Signatures and instances......Page 315 13.4 A tour of the built-in Haskell classes......Page 322 13.5 Type checking and type inference: an overview......Page 331 13.6 Monomorphic type checking......Page 332 13.7 Polymorphic type checking......Page 335 13.8 Type checking and classes......Page 343 Summary......Page 345 Chapter 14: Algebraic types......Page 346 14.1 Algebraic type definitions revisited......Page 347 14.2 Recursive algebraic types......Page 349 14.3 Polymorphic algebraic types......Page 356 14.4 Modelling program errors......Page 360 14.5 Design with algebraic data types......Page 364 14.6 Algebraic types and type classes......Page 368 14.7 Reasoning about algebraic types......Page 373 Summary......Page 377 15.1 Modules in Haskell......Page 380 15.2 Modular design......Page 384 15.3 Coding and decoding......Page 385 15.4 Implementation – I......Page 387 15.5 Building Huffman trees......Page 390 15.6 Design......Page 391 15.7 Implementation – II......Page 392 Summary......Page 399 16.1 Type representations......Page 400 16.2 The Haskell abstract data type mechanism......Page 402 16.3 Queues......Page 406 16.4 Design......Page 409 16.5 Simulation......Page 411 16.6 Implementing the simulation......Page 413 16.7 Search trees......Page 417 16.8 Sets......Page 423 16.9 Relations and graphs......Page 428 16.10 Commentary......Page 436 Summary......Page 437 Chapter 17: Lazy programming......Page 438 17.1 Lazy evaluation......Page 439 17.2 Calculation rules and lazy evaluation......Page 441 17.3 List comprehensions revisited......Page 444 17.4 Data-directed programming......Page 451 17.5 Case study: parsing expressions......Page 455 17.6 Infinite lists......Page 465 17.7 Why infinite lists?......Page 470 17.8 Case study: simulation......Page 473 17.9 Proof revisited......Page 475 Summary......Page 480 18.1 I/O programming......Page 482 18.2 Further I/O......Page 485 18.3 The calculator......Page 488 18.4 The do notation revisited......Page 491 18.5 Monads: languages for functional programming......Page 492 18.6 Example: monadic computation over trees......Page 499 Summary......Page 505 19.1 Programming languages everywhere......Page 506 19.2 Why DSLs in Haskell?......Page 509 19.3 Shallow and deep embeddings......Page 510 19.4 A DSL for regular expressions......Page 513 19.5 Monadic DSLs......Page 518 19.6 DSLs for computation: generating data in QuickCheck......Page 521 19.7 Taking it further......Page 526 Summary......Page 527 20.1 Complexity of functions......Page 528 20.2 The complexity of calculations......Page 532 20.3 Implementations of sets......Page 536 20.4 Space behaviour......Page 537 20.5 Folding revisited......Page 540 20.6 Avoiding recomputation: memoization......Page 546 Summary......Page 551 Chapter 21: Conclusion......Page 552 Appendix A: Functional, imperative and OO programming......Page 558 Appendix B: Glossary......Page 566 Appendix C: Haskell operators......Page 574 Appendix D: Haskell practicalities......Page 576 Appendix E: GHCi errors......Page 578 Appendix F: Project ideas......Page 584 Bibliography......Page 590 Index......Page 594

The third edition of Haskell: The Craft of Functional Programming is essential reading for beginners to functional programming and newcomers to the Haskell programming language. The emphasis is on the process of crafting programs and the text contains many examples and running case studies, as well as advice on program design, testing, problem solving and how to avoid common pitfalls.

Revisions to this new edition include new material on testing and domain-specific languages and a variety of new examples and case studies, including simple games. Existing material has been expanded and re-ordered, so that some concepts - such as simple data types and input/output - are presented at an earlier stage. The running example of Pictures is now implemented using web browser graphics as well as lists of strings.

The book uses GHCi, the interactive version of the Glasgow Haskell Compiler, as its implementation of choice. It has also been revised to include material about the Haskell Platform, and the Hackage online database of Haskell libraries. In particular, readers are given detailed guidance about how to find their way around what is available in these systems.

An accompanying web site supports the book, containing all the program code, further teaching materials and other useful resources.

Simon Thompson is Professor of Logic and Computation in the School of Computing at the University of Kent. His research and teaching interests include functional programming and logical aspects of computer science. Simon has written three other books: Erlang Programming (co-authored with Francesco Cesarini), Miranda: The Craft of Functional Programming and Type Theory and Functional Programming.

Introducing functional programming in the Haskell language, this book is written for students and programmers with little or no experience. It emphasises the process of crafting programmes, problem solving and avoiding common programming pitfalls.Covering basic functional programming, through abstraction to larger scale programming, students are lead step by step through the basics, before being introduced to more advanced topics.This edition includes new material on testing and domain-specific languages and a variety of new examples and case studies, including simple games. Existing material has been expanded and re-ordered, so that some concepts – such as simple data types and input/output – are presented at an earlier stage.