The Haskell Road to Logic, Maths and Programming

Description

The purpose of this book is to teach logic and mathematical reasoning in practice, and to connect logical reasoning with computer programming in Haskell. Haskell emerged in the last decade as a standard for lazy functional programming, a programming style where arguments are evaluated only when the value is actually needed. Haskell is a marvellous demonstration tool for logic and maths because its functional character allows implementations to remain very close to the concepts that get implemented, while the laziness permits smooth handling of infinite data structures. This book does not assume the reader to have previous experience with either programming or construction of formal proofs, but acquaintance with mathematical notation, at the level of secondary school mathematics is presumed. Everything one needs to know about mathematical reasoning or programming is explained as we go along. After proper digestion of the material in this book the reader will be able to write interesting programs, reason about their correctness, and document them in a clear fashion. The reader will also have learned how to set up mathematical proofs in a structured way, and how to read and digest mathematical proofs written by others. Contents Preface Purpose Logic in Practice How to Use the Book Exercises Book Website and Contact Acknowledgments GettingStarted Preview 1.1 Starting up the Haskell Interpreter 1.2 Implementing a Prime NumberTest 1.3 Haskell Type Declarations 1.4 Identifiers in Haskell 1.5 Playing the Haskell Game 1.6 Haskell Types 1.7 The Prime Factorization Algorithm 1.8 The map and filter Functions 1.9 Haskell Equations and Equational Reasoning 1.10 FurtherReading Talking about Mathematical Objects Preview 2.1 Logical Connectives and their Meanings 2.2 Logical Validity and Related Notions 2.3 Making Symbolic Form Explicit 2.4 Lambda Abstraction 2.5 Definitions and Implementations 2.6 Abstract Formulas and Concrete Structures 2.7 Logical Handling of the Quantifiers 2.8 Quantifiers as Procedures 2.9 Further Reading The Use of Logic: Proof Preview 3.1 Proof Style 3.2 Proof Recipes 3.3 Rules for the Connectives 3.4 Rules for the Quantifiers 3.5 Summary of the Proof Recipes 3.6 Some Strategic Guidelines 3.7 Reasoning and Computation with Primes 3.8 Further Reading Sets,Types and Lists Preview 4.1 Let’s Talk About Sets 4.2 Paradoxes,Types and Type Classes 4.3 SpecialSets 4.4 Algebra of Sets 4.5 Ordered Pairs and Products 4.6 Lists and List Operations 4.7 List Comprehension and Database Query 4.8 Using Lists to Represent Sets 4.9A Data Type for Sets 4.10 Further Reading Relations Preview 5.1 The Notion of a Relation 5.2 Properties of Relations 5.3 Implementing Relations as Sets of Pairs 5.4 Implementing Relations as Characteristic Functions 5.5 Equivalence Relations 5.6 Equivalence Classes and Partitions 5.7 Integer Partitions 5.8 Further Reading Functions Preview 6.1 Basic Notions 6.2 Surjections,Injections,Bijections 6.3 Function Composition 6.4 Inverse Function 6.5 Partial Functions 6.6 Functions as Partitions 6.7 Products 6.8 Congruences 6.9 FurtherReading InductionandRecursion Preview 7.1 Mathematical Induction 7.2 Recursion over the Natural Numbers 7.3 The Nature of Recursive Definitions 7.4 Induction and Recursion over Trees 7.5 Induction and Recursion over Lists 7.6 Some Variations on the Tower of Hanoi 7.7 Induction and Recursion over Other Data Structures 7.8 Further Reading Working with Numbers Preview 8.1 A Module for Natural Numbers 8.2 GCD and the Fundamental Theorem of Arithmetic 8.3 Integers 8.4 Implementing Integer Arithmetic 8.5 Rational Numbers 8.6 Implementing Rational Arithmetic 8.7 Irrational Numbers 8.8 The Mechanic’s Rule 8.9 Reasoning about Reals 8.10 ComplexNumbers 8.11 Further Reading Polynomials Preview 9.1Difference Analysis of Polynomial Sequences 9.2 Gaussian Elimination 9.3 Polynomials and the Binomial Theorem 9.4 Polynomials for Combinatorial Reasoning 9.5 Further Reading Corecursion Preview 10.1 Corecursive Definitions 10.2 Processesand Labeled Transition Systems 10.3 Proof by Approximation 10.4 Proof by Coinduction 10.5 Power Series and Generating Functions 10.6 Exponential Generating Functions 10.7 Further Reading FiniteandInfiniteSets Preview 11.1MoreonMathematicalInduction 11.2 Equipollence 11.3 Infinite Sets 11.4 Cantor’s World Implemented 11.5 *Cardinal Numbers *Further Exercises The Greek Alphabet Bibliography Index