| |
| |
| Preface | |
| |
| |
| |
| Introducing functional programming | |
| |
| |
| |
| Computers and modelling | |
| |
| |
| |
| What is a function? | |
| |
| |
| |
| Pictures and functions | |
| |
| |
| |
| Types | |
| |
| |
| |
| The Haskell programming language | |
| |
| |
| |
| Expressions and evaluation | |
| |
| |
| |
| Definitions | |
| |
| |
| |
| Function definitions | |
| |
| |
| |
| Types and functional programming | |
| |
| |
| |
| Calculation and evaluation | |
| |
| |
| |
| The essence of Haskell programming | |
| |
| |
| |
| Domain-specific languages | |
| |
| |
| |
| Two models of Pictures | |
| |
| |
| |
| Tests, properties and proofs | |
| |
| |
| |
| Getting started with Haskell and GHCi | |
| |
| |
| |
| A first Haskell program | |
| |
| |
| |
| Using Haskell in practice | |
| |
| |
| |
| Using GHCi | |
| |
| |
| |
| The standard prelude and the Haskell libraries | |
| |
| |
| |
| Modules | |
| |
| |
| |
| A second example: pictures | |
| |
| |
| |
| Errors and error messages | |
| |
| |
| |
| Basic types and definitions | |
| |
| |
| |
| The Booleans: Bool | |
| |
| |
| |
| The integers: Integer and Int | |
| |
| |
| |
| Overloading | |
| |
| |
| |
| Guards | |
| |
| |
| |
| Characters and strings | |
| |
| |
| |
| Floating-point numbers: Float | |
| |
| |
| |
| Syntax | |
| |
| |
| |
| Designing and writing programs | |
| |
| |
| |
| Where do I start? Designing a program in Haskell | |
| |
| |
| |
| Solving a problem in steps: local definitions | |
| |
| |
| |
| Defining types for ourselves: enumerated types | |
| |
| |
| |
| Recursion | |
| |
| |
| |
| Primitive recursion in practice | |
| |
| |
| |
| Extended exercise: pictures | |
| |
| |
| |
| General forms of recursion | |
| |
| |
| |
| Program testing | |
| |
| |
| |
| Data types, tuples and lists | |
| |
| |
| |
| Introducing tuples and lists | |
| |
| |
| |
| Tuple types | |
| |
| |
| |
| Introducing algebraic types | |
| |
| |
| |
| Our approach to lists | |
| |
| |
| |
| Lists in Haskell | |
| |
| |
| |
| List comprehensions | |
| |
| |
| |
| A library database | |
| |
| |
| |
| Programming with lists | |
| |
| |
| |
| Generic functions: polymorphism | |
| |
| |
| |
| Haskell list functions in the Prelude | |
| |
| |
| |
| Finding your way around the Haskell libraries | |
| |
| |
| |
| The Picture example: implementation | |
| |
| |
| |
| Extended exercise: alternative implementations of pictures | |
| |
| |
| |
| Extended exercise: positioned pictures | |
| |
| |
| |
| Extended exercise: supermarket billing | |
| |
| |
| |
| Extended exercise: cards and card games | |
| |
| |
| |
| Defining functions over lists | |
| |
| |
| |
| Pattern matching revisited | |
| |
| |
| |
| Lists and list patterns | |
| |
| |
| |
| Primitive recursion over lists | |
| |
| |
| |
| Finding primitive recursive definitions | |
| |
| |
| |
| General recursions over lists | |
| |
| |
| |
| Example: text processing | |
| |
| |
| |
| Playing the game: I/O in Haskell | |
| |
| |
| |
| Rock - Paper - Scissors: strategies | |
| |
| |
| |
| Why is I/O an issue? | |
| |
| |
| |
| The basics of input/output | |
| |
| |
| |
| The do notation | |
| |
| |
| |
| Loops and recursion | |
| |
| |
| |
| Rock - Paper - Scissors: playing the game | |
| |
| |
| |
| Reasoning about programs | |
| |
| |
| |
| Understanding definitions | |
| |
| |
| |
| Testing and proof | |
| |
| |
| |
| Definedness, termination and finiteness | |
| |
| |
| |
| A little logic | |
| |
| |
| |
| Induction | |
| |
| |
| |
| Further examples of proofs by induction | |
| |
| |
| |
| Generalizing the proof goal | |
| |
| |
| |
| Generalization: patterns of computation | |
| |
| |
| |
| Patterns of computation over lists | |
| |
| |
| |
| Higher-order functions: functions as arguments | |
| |
| |
| |
| Folding and primitive recursion | |
| |
| |
| |
| Generalizing: splitting up lists | |
| |
| |
| |
| Case studies revisited | |
| |
| |
| |
| Higher-order functions | |
| |
| |
| |
| Operators: function composition and application | |
| |
| |
| |
| Expressions for functions: lambda abstractions | |
| |
| |
| |
| Partial application | |
| |
| |
| |
| Under the hood: curried functions | |
| |
| |
| |
| Defining higher-order functions | |
| |
| |
| |
| Verification and general functions | |
| |
| |
| |
| Developing higher-order programs | |
| |
| |
| |
| Revisiting the Picture example | |
| |
| |
| |
| Functions as data: strategy combinators | |
| |
| |
| |
| Functions as data: recognizing regular expressions | |
| |
| |
| |
| Case studies: functions as data | |
| |
| |
| |
| Example: creating an index | |
| |
| |
| |
| Development in practice | |
| |
| |
| |
| Understanding programs | |
| |
| |
| |
| Overloading, type classes and type checking | |
| |
| |
| |
| Why overloading? | |
| |
| |
| |
| Introducing classes | |
| |
| |
| |
| Signatures and instances | |
| |
| |
| |
| A tour of the built-in Haskell classes | |
| |
| |
| |
| Type checking and type inference: an overview | |
| |
| |
| |
| Monomorphic type checking | |
| |
| |
| |
| Polymorphic type checking | |
| |
| |
| |
| Type checking and classes | |
| |
| |
| |
| Algebraic types | |
| |
| |
| |
| Algebraic type definitions revisited | |
| |
| |
| |
| Recursive algebraic types | |
| |
| |
| |
| Polymorphic algebraic types | |
| |
| |
| |
| Modelling program errors | |
| |
| |
| |
| Design with algebraic data types | |
| |
| |
| |
| Algebraic types and type classes | |
| |
| |
| |
| Reasoning about algebraic types | |
| |
| |
| |
| Case study: Huffman codes | |
| |
| |
| |
| Modules in Haskell | |
| |
| |
| |
| Modular design | |
| |
| |
| |
| Coding and decoding | |
| |
| |
| |
| Implementation - I | |
| |
| |
| |
| Building Huffman trees | |
| |
| |
| |
| Design | |
| |
| |
| |
| Implementation - II | |
| |
| |
| |
| Abstract data types | |
| |
| |
| |
| Type representations | |
| |
| |
| |
| The Haskell abstract data type mechanism | |
| |
| |
| |
| Queues | |
| |
| |
| |
| Design | |
| |
| |
| |
| Simulation | |
| |
| |
| |
| Implementing the simulation | |
| |
| |
| |
| Search trees | |
| |
| |
| |
| Sets | |
| |
| |
| |
| Relations and graphs | |
| |
| |
| |
| Commentary | |
| |
| |
| |
| Lazy programming | |
| |
| |
| |
| Lazy evaluation | |
| |
| |
| |
| Calculation rules and lazy evaluation | |
| |
| |
| |
| List comprehensions revisited | |
| |
| |
| |
| Data-directed programming | |
| |
| |
| |
| Case study: parsing expressions | |
| |
| |
| |
| Infinite lists | |
| |
| |
| |
| Why infinite lists? | |
| |
| |
| |
| Case study: simulation | |
| |
| |
| |
| Proof revisited | |
| |
| |
| |
| Programming with monads | |
| |
| |
| |
| I/O programming | |
| |
| |
| |
| Further I/O | |
| |
| |
| |
| The calculator | |
| |
| |
| |
| The do notation revisited | |
| |
| |
| |
| Monads: languages for functional programming | |
| |
| |
| |
| Example: monadic computation over trees | |
| |
| |
| |
| Domain-specific languages | |
| |
| |
| |
| Programming languages everywhere | |
| |
| |
| |
| Why DSLs in Haskell? | |
| |
| |
| |
| Shallow and deep embeddings | |
| |
| |
| |
| A DSL for regular expressions | |
| |
| |
| |
| Monadic DSLs | |
| |
| |
| |
| DSLs for computation: generating data in QuickCheck | |
| |
| |
| |
| Taking it further | |
| |
| |
| |
| Time and space behaviour | |
| |
| |
| |
| Complexity of functions | |
| |
| |
| |
| The complexity of calculations | |
| |
| |
| |
| Implementations of sets | |
| |
| |
| |
| Space behaviour | |
| |
| |
| |
| Folding revisited | |
| |
| |
| |
| Avoiding recomputation: memoization | |
| |
| |
| |
| Conclusion | |
| |
| |
| Appendices | |
| |
| |
| |
| Functional, imperative and OO programming | |
| |
| |
| |
| Glossary | |
| |
| |
| |
| Haskell operators | |
| |
| |
| |
| Haskell practicalities | |
| |
| |
| |
| GHCi errors | |
| |
| |
| |
| Project ideas | |
| |
| |
| Bibliography | |