Miranda
The Craft of Functional Programming
Simon Thompson
Preface
Part I Basic Functional Programming
Chapter 1 Introducing functional programming
1.1 What is Functional Programming?
1.2 Miranda
1.3 Practical work
Chapter 2 Basic types and simple programs
2.1 The numbers: Integers
2.2 Programming with integers
2.3 Syntax
2.4 Definitions: Patterns
2.5 Programming with Booleans
2.6 Characters and Strings
2.7 The numbers: Fractions
2.8 Programming with numbers and strings
2.9 Data structures: Tuples
2.10 Function Definitions
2.11 Programming with local definitions
2.12 Example: Quadratic equations
2.13 Design
Chapter 3 Reasoning about programs
3.1 Informal proof: an introduction
3.2 Proof by Induction
3.3 Building induction proofs
Chapter 4 Data structures: Lists
4.1 Lists in Miranda
4.2 Defining functions over lists
4.3 Designing functions over lists
4.4 A library database
4.5 List comprehensions
4.6 Extended exercise: supermarket billing
4.7 Example: Text Processing
4.8 Definition forms
4.9 Program design
Chapter 5 Reasoning about lists
5.1 Structural induction
5.2 Proofs by structural induction
5.3 Case studies
5.4 Generalizing the proof goal
Part II Abstraction
Chapter 6 Generalization
6.1 Functions as arguments
6.2 Polymorphism
6.3 Putting the two together
6.4 Using the higher-order functions
6.5 Generalizing: splitting up lists
Chapter 7 Further Generalization
7.1 Function composition
7.2 Functions as results
7.3 Partial Application
7.4 Examples
7.5 Currying and uncurrying
7.6 Example: creating an index
7.7 Design revisited
7.8 Verification
Chapter 8 Types in Miranda
8.1 Monomorphic types
8.2 Polymorphic types
8.3 Polymorphic Type Checking
8.4 Special functions
Part III Larger-scale programming
Chapter 9 Algebraic types
9.1 Introduction
9.2 Recursive Types
9.3 Polymorphic algebraic types
9.4 Case study: Program Errors
9.5 Design with Algebraic Data Types
9.6 Reasoning about algebraic types
Chapter 10 Case study: Huffman codes
10.1 Modules in Miranda
10.2 Modular design
10.3 Coding and decoding
10.4 Implementation - I
10.5 Building Huffman trees
10.6 Design
10.7 Implementation - II
Chapter 11 Type abstraction
11.1 Type representations
11.2 The Miranda abstype mechanism
11.3 Example: queues
11.4 Design
11.5 Example: Simulation
11.6 Implementing the simulation
11.7 Example: Search trees
11.8 Case Study: Sets
11.9 Relations and graphs
Chapter 12 Lazy evaluation & Lists revisited
12.1 Introduction
12.2 Calculation Rules
12.3 List comprehensions revisited
12.4 Data on demand
12.5 Case study: Parsing expressions
Chapter 13 Infinite lists
13.1 Infinite lists
13.2 Why infinite lists?
13.3 Case study: Simulation
13.4 Writing interactive programs
13.5 A library for interactions
13.6 Implementing the abstype of interactions
13.7 Proof revisited
Chapter 14 Program behaviour
14.1 Complexity of functions
14.2 The complexity of calculations
14.3 Implementations of sets
14.4 Space behaviour
14.5 Folding revisited
14.6 Avoiding re-computation: memoization
Appendix A Functional and Imperative programming
Appendix B Further reading
Appendix C Glossary
Appendix D Understanding programs
Appendix E Miranda operators
Appendix F Miranda Errors
Appendix G Some Useful Functions
Bibliography
Index
Up