Real World Haskell Bryan O’Sullivan, John Goerzen, Don Stewart Real World Haskell by Bryan O’Sullivan, John Goerzen, and Don Stewart Copyright © 2009 Bryan O’Sullivan, John Goerzen, and Donald Stewart Printed in the United States of America. Published by O’Reilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 95472. Printing History: November 2008: First Edition. ISBN: 978-0-596-51498-3 [M] 1226696198 Contents Preface ................................................................... xxiii 1. Getting Started ......................................................... 1 Your Haskell Environment 1 Getting Started with ghci, the Interpreter 2 Basic Interaction: Using ghci as a Calculator 3 Simple Arithmetic 3 An Arithmetic Quirk: Writing Negative Numbers 4 Boolean Logic, Operators, and Value Comparisons 5 Operator Precedence and Associativity 7 Undefined Values, and Introducing Variables 8 Dealing with Precedence and Associativity Rules 8 Command-Line Editing in ghci 9 Lists 9 Operators on Lists 11 Strings and Characters 11 First Steps with Types 12 A Simple Program 15 2. Types and Functions .................................................... 17 Why Care About Types? 17 Haskell’s Type System 18 Strong Types 18 Static Types 19 Type Inference 20 What to Expect from the Type System 20 Some Common Basic Types 21 Function Application 22 Useful Composite Data Types: Lists and Tuples 23 Functions over Lists and Tuples 25 Passing an Expression to a Function 26 Function Types and Purity 27 Haskell Source Files, and Writing Simple Functions 27 Just What Is a Variable, Anyway? 28 Conditional Evaluation 29 Understanding Evaluation by Example 32 Lazy Evaluation 32 A More Involved Example 33 Recursion 34 Ending the Recursion 35 Returning from the Recursion 35 What Have We Learned? 36 Polymorphism in Haskell 36 Reasoning About Polymorphic Functions 38 Further Reading 38 The Type of a Function of More Than One Argument 38 Why the Fuss over Purity? 39 Conclusion 40 3. Defining Types, Streamlining Functions ................................... 41 Defining a New Data Type 41 Naming Types and Values 43 Type Synonyms 43 Algebraic Data Types 44 Tuples, Algebraic Data Types, and When to Use Each 45 Analogues to Algebraic Data Types in Other Languages 47 Pattern Matching 50 Construction and Deconstruction 51 Further Adventures 52 Variable Naming in Patterns 53 The Wild Card Pattern 53 Exhaustive Patterns and Wild Cards 54 Record Syntax 55 Parameterized Types 57 Recursive Types 58 Reporting Errors 60 A More Controlled Approach 61 Introducing Local Variables 61 Shadowing 62 The where Clause 63 Local Functions, Global Variables 63 The Offside Rule and Whitespace in an Expression 64 A Note About Tabs Versus Spaces 66 The Offside Rule Is Not Mandatory 66 The case Expression 66 Common Beginner Mistakes with Patterns 67 Incorrectly Matching Against a Variable 67 Incorrectly Trying to Compare for Equality 68 Conditional Evaluation with Guards 68 4. Functional Programming ................................................ 71 Thinking in Haskell 71 A Simple Command-Line Framework 71 Warming Up: Portably Splitting Lines of Text 72 A Line-Ending Conversion Program 75 Infix Functions 76 Working with Lists 77 Basic List Manipulation 78 Safely and Sanely Working with Crashy Functions 79 Partial and Total Functions 79 More Simple List Manipulations 80 Working with Sublists 81 Searching Lists 82 Working with Several Lists at Once 83 Special String-Handling Functions 84 How to Think About Loops 84 Explicit Recursion 85 Transforming Every Piece of Input 87 Mapping over a List 88 Selecting Pieces of Input 90 Computing One Answer over a Collection 90 The Left Fold 92 Why Use Folds, Maps, and Filters? 93 Folding from the Right 94 Left Folds, Laziness, and Space Leaks 96 Further Reading 99 Anonymous (lambda) Functions 99 Partial Function Application and Currying 100 Sections 102 As-patterns 103 Code Reuse Through Composition 104 Use Your Head Wisely 107 Tips for Writing Readable Code 107 Space Leaks and Strict Evaluation 108 Avoiding Space Leaks with seq 108 Learning to Use seq 109 5. Writing a Library: Working with JSON Data ................................ 111 A Whirlwind Tour of JSON 111 Representing JSON Data in Haskell 111 The Anatomy of a Haskell Module 113 Compiling Haskell Source 114 Generating a Haskell Program and Importing Modules 114 Printing JSON Data 115 Type Inference Is a Double-Edged Sword 117 A More General Look at Rendering 118 Developing Haskell Code Without Going Nuts 119 Pretty Printing a String 120 Arrays and Objects, and the Module Header 122 Writing a Module Header 123 Fleshing Out the Pretty-Printing Library 124 Compact Rendering 127 True Pretty Printing 128 Following the Pretty Printer 129 Creating a Package 131 Writing a Package Description 131 GHC’s Package Manager 133 Setting Up, Building, and Installing 133 Practical Pointers and Further Reading 134 6. Using Typeclasses ..................................................... 135 The Need for Typeclasses 135 What Are Typeclasses? 136 Declaring Typeclass Instances 139 Important Built-in Typeclasses 139 Show 139 Read 141 Serialization with read and show 143 Numeric Types 144 Equality, Ordering, and Comparisons 148 Automatic Derivation 148 Typeclasses at Work: Making JSON Easier to Use 149 More Helpful Errors 151 Making an Instance with a Type Synonym 151 Living in an Open World 152 When Do Overlapping Instances Cause Problems? 153 Relaxing Some Restrictions on Typeclasses 154 How Does Show Work for Strings? 155 How to Give a Type a New Identity 155 Differences Between Data and Newtype Declarations 157 Summary: The Three Ways of Naming Types 158 JSON Typeclasses Without Overlapping Instances 159 The Dreaded Monomorphism Restriction 162 Conclusion 163 7. I/O ................................................................. 165 Classic I/O in Haskell 165 Pure Versus I/O 168 Why Purity Matters 169 Working with Files and Handles 169 More on openFile 171 Closing Handles 172 Seek and Tell 172 Standard Input, Output, and Error 173 Deleting and Renaming Files 174 Temporary Files 174 Extended Example: Functional I/O and Temporary Files 175 Lazy I/O 178 hGetContents 178 readFile and writeFile 180 A Word on Lazy Output 181 interact 181 The IO Monad 183 Actions 183 Sequencing 186 The True Nature of Return 187 Is Haskell Really Imperative? 188 Side Effects with Lazy I/O 188 Buffering 189 Buffering Modes 189 Flushing The Buffer 190 Reading Command-Line Arguments 190 Environment Variables 191 8. Efficient File Processing, Regular Expressions, and Filename Matching ......... 193 Efficient File Processing 193 Binary I/O and Qualified Imports 194 Text I/O 195 Filename Matching 197 Regular Expressions in Haskell 198 The Many Types of Result 198 More About Regular Expressions 200 Mixing and Matching String Types 200 Other Things You Should Know 201 Translating a glob Pattern into a Regular Expression 202 An important Aside: Writing Lazy Functions 205 Making Use of Our Pattern Matcher 206 Handling Errors Through API Design 210 Putting Our Code to Work 211 9. I/O Case Study: A Library for Searching the Filesystem ....................... 213 The find Command 213 Starting Simple: Recursively Listing a Directory 213 Revisiting Anonymous and Named Functions 214 Why Provide Both mapM and forM? 215 A Naive Finding Function 215 Predicates: From Poverty to Riches, While Remaining Pure 217 Sizing a File Safely 219 The Acquire-Use-Release Cycle 221 A Domain-Specific Language for Predicates 221 Avoiding Boilerplate with Lifting 223 Gluing Predicates Together 224 Defining and Using New Operators 225 Controlling Traversal 226 Density, Readability, and the Learning Process 228 Another Way of Looking at Traversal 229 Useful Coding Guidelines 232 Common Layout Styles 233 10. Code Case Study: Parsing a Binary Data Format ............................ 235 Grayscale Files 235 Parsing a Raw PGM File 236 Getting Rid of Boilerplate Code 238 Implicit State 239 The Identity Parser 240 Record Syntax, Updates, and Pattern Matching 241 A More Interesting Parser 242 Obtaining and Modifying the Parse State 242 Reporting Parse Errors 243 Chaining Parsers Together 243 Introducing Functors 244 Constraints on Type Definitions Are Bad 247 Infix Use of fmap 248 Flexible Instances 248 Thinking More About Functors 249 Writing a Functor Instance for Parse 250 Using Functors for Parsing 251 Rewriting Our PGM Parser 252 Future Directions 254 11. Testing and Quality Assurance .......................................... 255 QuickCheck: Type-Based Testing 256 Testing for Properties 257 Testing Against a Model 259 Testing Case Study: Specifying a Pretty Printer 259 Generating Test Data 259 Testing Document Construction 262 Using Lists as a Model 263 Putting It All Together 264 Measuring Test Coverage with HPC 265 12. Barcode Recognition .................................................. 269 A Little Bit About Barcodes 269 EAN-13 Encoding 270 Introducing Arrays 270 Arrays and Laziness 273 Folding over Arrays 273 Modifying Array Elements 274 Encoding an EAN-13 Barcode 275 Constraints on Our Decoder 275 Divide and Conquer 276 Turning a Color Image into Something Tractable 278 Parsing a Color Image 278 Grayscale Conversion 279 Grayscale to Binary and Type Safety 279 What Have We Done to Our Image? 280 Finding Matching Digits 282 Run Length Encoding 282 Scaling Run Lengths, and Finding Approximate Matches 283 List Comprehensions 284 Remembering a Match’s Parity 285 Chunking a List 287 Generating a List of Candidate Digits 287 Life Without Arrays or Hash Tables 288 A Forest of Solutions 288 A Brief Introduction to Maps 289 Further Reading 292 Turning Digit Soup into an Answer 292 Solving for Check Digits in Parallel 292 Completing the Solution Map with the First Digit 294 Finding the Correct Sequence 295 Working with Row Data 295 Pulling It All Together 296 A Few Comments on Development Style 297 13. Data Structures ....................................................... 299 Association Lists 299 Maps 301 Functions Are Data, Too 303 Extended Example: /etc/passwd 304 Extended Example: Numeric Types 307 First Steps 309 Completed Code 311 Taking Advantage of Functions as Data 317 Turning Difference Lists into a Proper Library 318 Lists, Difference Lists, and Monoids 320 General-Purpose Sequences 322 14. Monads ............................................................. 325 325 Revisiting Earlier Code Examples 325 Maybe Chaining 325 Implicit State 326 Looking for Shared Patterns 327 The Monad Typeclass 329 And Now, a Jargon Moment 330 Using a New Monad: Show Your Work! 331 Information Hiding 331 Controlled Escape 332 Leaving a Trace 332 Using the Logger Monad 333 Mixing Pure and Monadic Code 334 Putting a Few Misconceptions to Rest 336 Building the Logger Monad 336 Sequential Logging, Not Sequential Evaluation 337 The Writer Monad 337 The Maybe Monad 338 Executing the Maybe Monad 338 Maybe at Work, and Good API Design 338 The List Monad 340 Understanding the List Monad 342 Putting the List Monad to Work 343