Haskell: The craft of functional programming

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