Programming in Haskell

"Haskell is a purely functional language that allows programmers to rapidly develop clear, concise, and correct software. The language has grown in popularity in recent years, both in teaching and in industry. This book is based on the author's experience of teaching Haskell for more than twenty years. All concepts are explained from first principles and no programming experience is required, making this book accessible to a broad spectrum of readers. While Part I focuses on basic concepts, Part II introduces the reader to more advanced topics. This new edition has been extensively updated and expanded to include recent and more advanced features of Haskell, new examples and exercises, selected solutions, and freely downloadable lecture slides and example code. The presentation is clean and simple, while also being fully compliant with the latest version of the language, including recent changes concerning applicative, monadic, foldable, and traversable types"-- Provided by publisher Foreword Preface Part I. Basic Concepts 1 Introduction 1.1 Functions 1.2 Functional programming 1.3 Features of Haskell 1.4 Historical background 1.5 A taste of Haskell 1.6 Chapter remarks 1.7 Exercises 2 First steps 2.1 Glasgow Haskell Compiler 2.2 Installing and starting 2.3 Standard prelude 2.4 Function application 2.5 Haskell scripts 2.6 Chapter remarks 2.7 Exercises 3 Types and classes 3.1 Basic concepts 3.2 Basic types 3.3 List types 3.4 Tuple types 3.5 Function types 3.6 Curried functions 3.7 Polymorphic types 3.8 Overloaded types 3.9 Basic classes 3.10 Chapter remarks 3.11 Exercises 4 Defining functions 4.1 New from old 4.2 Conditional expressions 4.3 Guarded equations 4.4 Pattern matching 4.5 Lambda expressions 4.6 Operator sections 4.7 Chapter remarks 4.8 Exercises 5 List comprehensions 5.1 Basic concepts 5.2 Guards 5.3 The zip function 5.4 String comprehensions 5.5 The Caesar cipher 5.6 Chapter remarks 5.7 Exercises 6 Recursive functions 6.1 Basic concepts 6.2 Recursion on lists 6.3 Multiple arguments 6.4 Multiple recursion 6.5 Mutual recursion 6.6 Advice on recursion 6.7 Chapter remarks 6.8 Exercises 7 Higher-order functions 7.1 Basic concepts 7.2 Processing lists 7.3 The foldr function 7.4 The foldl function 7.5 The composition operator 7.6 Binary string transmitter 7.7 Voting algorithms 7.8 Chapter remarks 7.9 Exercises 8 Declaring types and classes 8.1 Type declarations 8.2 Data declarations 8.3 Newtype declarations 8.4 Recursive types 8.5 Class and instance declarations 8.6 Tautology checker 8.7 Abstract machine 8.8 Chapter remarks 8.9 Exercises 9 The countdown problem 9.1 Introduction 9.2 Arithmetic operators 9.3 Numeric expressions 9.4 Combinatorial functions 9.5 Formalising the problem 9.6 Brute force solution 9.7 Performance testing 9.8 Combining generation and evaluation 9.9 Exploiting algebraic properties 9.10 Chapter remarks 9.11 Exercises Part II. Going Further 10 Interactive programming 10.1 The problem 10.2 The solution 10.3 Basic actions 10.4 Sequencing 10.5 Derived primitives 10.6 Hangman 10.7 Nim 10.8 Life 10.9 Chapter remarks 10.10 Exercises 11 Unbeatable tic-tac-toe 11.1 Introduction 11.2 Basic declarations 11.3 Grid utilities 11.4 Displaying a grid 11.5 Making a move 11.6 Reading a number 11.7 Human vs human 11.8 Game trees 11.9 Pruning the tree 11.10 Minimax algorithm 11.11 Human vs computer 11.12 Chapter remarks 11.13 Exercises 12 Monads and more 12.1 Functors 12.2 Applicatives 12.3 Monads 12.4 Chapter remarks 12.5 Exercises 13 Monadic parsing 13.1 What is a parser? 13.2 Parsers as functions 13.3 Basic definitions 13.4 Sequencing parsers 13.5 Making choices 13.6 Derived primitives 13.7 Handling spacing 13.8 Arithmetic expressions 13.9 Calculator 13.10 Chapter remarks 13.11 Exercises 14 Foldables and friends 14.1 Monoids 14.2 Foldables 14.3 Traversables 14.4 Chapter remarks 14.5 Exercises 15 Lazy evaluation 15.1 Introduction 15.2 Evaluation strategies 15.3 Termination 15.4 Number of reductions 15.5 Infinite structures 15.6 Modular programming 15.7 Strict application 15.8 Chapter remarks 15.9 Exercises 16 Reasoning about programs 16.1 Equational reasoning 16.2 Reasoning about Haskell 16.3 Simple examples 16.4 Induction on numbers 16.5 Induction on lists 16.6 Making append vanish 16.7 Compiler correctness 16.8 Chapter remarks 16.9 Exercises 17 Calculating compilers 17.1 Introduction 17.2 Syntax and semantics 17.3 Adding a stack 17.4 Adding a continuation 17.5 Defunctionalising 17.6 Combining the steps 17.7 Chapter remarks 17.8 Exercises Appendix A. Selected solutions A.1 Introduction A.2 First steps A.3 Types and classes A.4 Defining functions A.5 List comprehensions A.6 Recursive functions A.7 Higher-order functions A.8 Declaring types and classes A.9 The countdown problem A.10 Interactive programming A.11 Unbeatable tic-tac-toe A.12 Monads and more A.13 Monadic parsing A.14 Foldables and friends A.15 Lazy evaluation A.16 Reasoning about programs A.17 Calculating compiler Appendix B. Standard prelude B.1 Basic classes B.2 Booleans B.3 Characters B.4 Strings B.5 Numbers B.6 Tuples B.7 Maybe B.8 Lists B.9 Functions B.10 Input/output B.11 Functors B.12 Applicatives B.13 Monads B.14 Alternatives B.15 MonadPlus B.16 Monoids B.17 Foldables B.18 Traversables Bibliography Index This edition has been extensively updated and expanded, with new chapters covering recent and more advanced features of Haskell, new examples and exercises, and freely downloadable lecture slides and example code. All concepts are explained from first principles and no programming experience is required, making it accessible to a broad range of readers.