Programming in Haskell

Haskell is one of the leading languages for teaching functional programming, enabling students to write simpler and cleaner code, and to learn how to structure and reason about programs. This introduction is ideal for beginners: it requires no previous programming experience and all concepts are explained from first principles via carefully chosen examples. Each chapter includes exercises that range from the straightforward to extended projects, plus suggestions for further reading on more advanced topics. The author is a leading Haskell researcher and instructor, well-known for his teaching skills. The presentation is clear and simple, and benefits from having been refined and class-tested over several years. The result is a text that can be used with courses, or for self-learning. Features include freely accessible Powerpoint slides for each chapter, solutions to exercises and examination questions (with solutions) available to instructors, and a downloadable code that's fully compliant with the latest Haskell release. Half-title 3 Title 4 Copyright 5 Dedication 6 Contents 8 Preface 12 Chapter 1 Introduction 14 1.1 Functions 14 1.2 Functional programming 15 1.3 Features of Haskell 17 1.4 Historical background 19 1.5 A taste of Haskell 19 1.6 Chapter remarks 22 1.7 Exercises 22 Chapter 2 First steps 23 2.1 The Hugs system 23 2.2 The standard prelude 23 2.3 Function application 25 2.4 Haskell scripts 26 My first script 26 Naming requirements 27 The layout rule 28 Comments 28 2.5 Chapter remarks 29 2.6 Exercises 29 Chapter 3 Types and classes 30 3.1 Basic concepts 30 3.2 Basic types 31 Bool – logical values 31 Char – single characters 31 String – strings of characters 32 Int – fixed-precision integers 32 Integer – arbitrary-precision integers 32 Float – single-precision floating-point numbers 32 3.3 List types 33 3.4 Tuple types 33 3.5 Function types 34 3.6 Curried functions 34 3.7 Polymorphic types 36 3.8 Overloaded types 36 3.9 Basic classes 37 Eq – equality types 37 Ord – ordered types 38 Show – showable types 39 Read – readable types 39 Num – numeric types 40 Integral – integral types 40 Fractional – fractional types 41 3.10 Chapter remarks 41 3.11 Exercises 41 Chapter 4 Defining functions 43 4.1 New from old 43 4.2 Conditional expressions 44 4.3 Guarded equations 44 4.4 Pattern matching 45 Tuple patterns 46 List patterns 46 Integer patterns 47 4.5 Lambda expressions 47 4.6 Sections 49 4.7 Chapter remarks 49 4.8 Exercises 50 Chapter 5 List comprehensions 51 5.1 Generators 51 5.2 Guards 52 5.3 The zip function 53 5.4 String comprehensions 54 5.5 The Caesar cipher 55 Encoding and decoding 56 Frequency tables 57 Cracking the cipher 58 5.6 Chapter remarks 59 5.7 Exercises 59 Chapter 6 Recursive functions 61 6.1 Basic concepts 61 6.2 Recursion on lists 62 6.3 Multiple arguments 65 6.4 Multiple recursion 66 6.5 Mutual recursion 66 6.6 Advice on recursion 68 Example – product 68 Step 1: define the type 68 Step 2: enumerate the cases 68 Step 3: define the simple cases 68 Step 4: define the other cases 68 Step 5: generalise and simplify 69 Example – drop 69 Step 1: define the type 69 Step 2: enumerate the cases 69 Step 3: define the simple cases 70 Step 4: define the other cases 70 Step 5: generalise and simplify 70 Example – init 71 Step 1: define the type 71 Step 2: enumerate the cases 71 Step 3: define the simple cases 71 Step 4: define the other cases 71 Step 5: generalise and simplify 72 6.7 Chapter remarks 72 6.8 Exercises 72 Chapter 7 Higher-order functions 74 7.1 Basic concepts 74 7.2 Processing lists 75 7.3 The foldr function 77 7.4 The foldl function 79 7.5 The composition operator 81 7.6 String transmitter 82 Binary numbers 82 Base conversion 83 Transmission 84 7.7 Chapter remarks 85 7.8 Exercises 85 Chapter 8 Functional parsers 87 8.1 Parsers 87 8.2 The parser type 88 8.3 Basic parsers 88 8.4 Sequencing 89 8.5 Choice 91 8.6 Derived primitives 91 8.7 Handling spacing 94 8.8 Arithmetic expressions 95 8.9 Chapter remarks 98 8.10 Exercises 98 Chapter 9 Interactive programs 100 9.1 Interaction 100 9.2 The input/output type 101 9.3 Basic actions 101 9.4 Sequencing 102 9.5 Derived primitives 103 9.6 Calculator 104 9.7 Game of life 107 9.8 Chapter remarks 110 9.9 Exercises 110 Chapter 10 Declaring types and classes 112 10.1 Type declarations 112 10.2 Data declarations 113 10.3 Recursive types 115 10.4 Tautology checker 118 10.5 Abstract machine 122 10.6 Class and instance declarations 124 Derived instances 125 Monadic types 126 10.7 Chapter remarks 127 10.8 Exercises 127 Chapter 11 The countdown problem 129 11.1 Introduction 129 11.2 Formalising the problem 130 11.3 Brute force solution 132 11.4 Combining generation and evaluation 133 11.5 Exploiting algebraic properties 134 11.6 Chapter remarks 136 11.7 Exercises 136 Chapter 12 Lazy evaluation 137 12.1 Introduction 137 12.2 Evaluation strategies 138 Lambda expressions 140 12.3 Termination 141 12.4 Number of reductions 142 12.5 Infinite structures 143 12.6 Modular programming 145 12.7 Strict application 147 12.8 Chapter remarks 150 12.9 Exercises 150 Chapter 13 Reasoning about programs 152 13.1 Equational reasoning 152 13.2 Reasoning about Haskell 153 13.3 Simple examples 154 13.4 Induction on numbers 155 13.5 Induction on lists 158 13.6 Making append vanish 159 13.7 Compiler correctness 163 13.8 Chapter remarks 167 13.9 Exercises 167 Appendix A Standard prelude 169 A.1 Classes 169 A.2 Logical values 170 A.3 Characters and strings 171 A.4 Numbers 172 A.5 Tuples 173 A.6 Maybe 173 A.7 Lists 173 A.8 Functions 177 A.9 Input/output 177 Appendix B Symbol table 179 Bibliography 180 Index 182 "Haskell is one of the leading languages for teaching functional programming, enabling students to write simpler and cleaner code, and to learn how to structure and reason about programs." "This introduction is ideal for beginners: it requires no previous programming experience and all concepts are explained from first principles with the aid of carefully chosen examples. Each chapter includes a series of exercises, ranging from the straightforward to extend projects, along with suggestions for further reading on more advanced topics. The presentation is clear and simple, and benefits from having been refined and class tested over several years."--Jacket