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.
Simon Thompson is Professor of Logic and Computation in the Computing Laboratory of the University of Kent, where he has taught computing at undergraduate and postgraduate levels for the past twenty five years, and where he has been department head for the last six.
His research work has centered on functional programming: program verification, type systems, and most recently development of software tools for functional programming languages. His team has built the HaRe tool for refactoring Haskell programs, and is currently developing Wrangler to do the same for Erlang. His research has been funded by various agencies including EPSRC and the European Framework programme. His training is as a mathematician: he has an MA in Mathematics from Cambridge and a D.Phil. in mathematical logic from Oxford.
He has written three books in his field of interest; Type Theory and Functional Programming published in 1991; Miranda: The Craft of Functional Programming (1995) and Haskell: The Craft of Functional Programming (2nd ed. 1999). These are all published by Addison Wesley.
Inhaltsangabe
Preface 1 Introducing functional programming 1.1 Computers and modelling 1.2 What is a function? 1.3 Pictures and functions 1.4 Types 1.5 The Haskell programming language 1.6 Expressions and evaluation 1.7 Definitions 1.8 Function definitions 1.9 Types and functional programming 1.10 Calculation and evaluation 1.11 The essence of Haskell programming 1.12 Domain-specific languages 1.13 Two models of Pictures 1.14 Tests, properties and proofs 2 Getting started with Haskell and GHCi 2.1 A first Haskell program 2.2 Using Haskell in practice 2.3 Using GHCi 2.4 The standard prelude and the Haskell libraries 2.5 Modules 2.6 A second example: Pictures 2.7 Errors and error messages 3 Basic types and definitions 3.1 The Booleans: Bool 3.2 The integers: Integer and Int 3.3 Overloading 3.4 Guards 3.5 Characters and strings 3.6 Floating-point numbers: Float 3.7 Syntax 4 Designing and writing programs 4.1 Where do I start? Designing a program in Haskell 4.2 Solving a problem in steps: local definitions 4.3 Defining types for ourselves: enumerated types 4.4 Recursion 4.5 Primitive recursion in practice 4.6 Extended exercise: pictures 4.7 General forms of recursion 4.8 Program testing 5 Data types, tuples and lists 5.1 Introducing tuples and lists 5.2 Tuple types 5.3 Introducing algebraic types 5.4 Our approach to lists 5.5 Lists in Haskell 5.6 List comprehensions 5.7 A library database 6 Programming with lists 6.1 Generic functions: polymorphism 6.2 Haskell list functions in the Prelude 6.3 Finding your way around the Haskell libraries 6.4 The Picture example: implementation 6.5 Extended exercise: alternative implementations of pictures 6.6 Extended exercise: positioned pictures 6.7 Extended exercise: supermarket billing 6.8 Extended exercise: cards and card games 7 Defining functions over lists 7.1 Pattern matching revisited 7.2 Lists and list patterns 7.3 Primitive recursion over lists 7.4 Finding primitive recursive definitions 7.5 General recursions over lists 7.6 Example: text processing 8 Playing the game: I/O in Haskell 8.1 Rock - Paper - Scissors: strategies 8.2 Why is I/O an issue? 8.3 The basics of input/output 8.4 The do notation 8.5 Loops and recursion 8.6 Rock - Paper - Scissors: playing the game 9 Reasoning about programs 9.1 Understanding definitions 9.2 Testing and proof 9.3 Definedness, termination and finiteness 9.4 A little logic 9.6 Further examples of proofs by induction 9.7 Generalizing the proof goal 10 Generalization: patterns of computation 10.1 Patterns of computation over lists 10.2 Higher-order functions: functions as arguments 10.3 Folding and primitive recursion 10.4 Generalizing: splitting up lists 10.5 Case studies revisited 11 Higher-order functions 11.1 Operators: function composition and application 11.2 Expressions for functions: lambda abstractions 11.3 Partial application 11.4 Under the hood: curried functions 11.5 Defining higher-order functions 11.6 Verification and general functions 12 Developing higher-order programs 12.1 Revisiting the Picture example 12.2 Functions as data: strategy combinators 12.3 Functions as data: recognising regular expressions 12.4 Case studies: functions as data 12.5 Example: creating an index 12.6 Development in practice 12.7 Understanding programs 13 Overloading, type classes and type checking 13.1 Why overloading? 13.2 Introducing classes 13.3 Signatures and instances 13.4 A tour of the built-in Haskell classes 13.5 Type checking and type inference: an overview 13.6 Monomorphic type checking 13.7 Polymorphic type checking 13.8 Type checking and classes 14 Algebraic types 14.1 Algebraic type definitions revisited 14.2 Recursive algebraic types 14.3 Polymorphic algebraic types 14.4 Modelling program errors 14.5 Design with algebraic data types 14.6 Algebraic types and type classes 14.7 Reasoning about algebraic types 15 Case study: Huffman codes 15.1 Modules in Haskell 15.2 Modular design 15.3 Coding and decoding 15.4 Implementation I 15.5 Building Huffman trees 15.6 Design 15.7 Implementation II 16 Abstract data types 16.1 Type representations 16.2 The Haskell abstract data type mechanism 16.3 Queues 16.4 Design 16.5 Simulation 16.6 Implementing the simulation 16.7 Search trees 16.8 Sets 16.9 Relations and graphs 16.10 Commentary 17 Lazy programming 17.1 Lazy evaluation 17.2 Calculation rules and lazy evaluation 17.3 List comprehensions revisited 17.4 Data-directed programming 17.5 Case study: parsing expressions 17.6 Infinite lists 17.7 Why infinite lists? 17.8 Case study: simulation 17.9 Proof revisited 18 Programming with monads 18.1 I/O programming 18.2 Further I/O 18.3 The calculator 18.4 The do notation revisited 18.5 Monads: languages for functional programming 18.6 Example: monadic computation over trees 19 Domain-Specific Languages 19.1 Programming languages everywhere 19.2 Why DSLs in Haskell? 19.3 Shallow and deep Embeddings 19.4 A DSL for regular expressions 19.5 Monadic DSLs 19.6 DSLs for computation: generating data in QuickCheck 19.7 Taking it further 20 Time and space behaviour 20.1 Complexity of functions 20.2 The complexity of calculations 20.3 Implementations of sets 20.4 Space behaviour 20.5 Folding revisited 20.6 Avoiding recomputation: memoization 21 Conclusion Appendices A Functional, imperative and 00 programming B Glossary C Haskell operators D Haskell practicalities E GHCi errors F Project ideas Bibliography
