Haskell Programming from First Principles (Christopher Allen, Julie Moronuki) (z-library.sk, 1lib.sk, z-lib.sk)

i Reader feedback “Astonishingly insightful examples. This book is a lot like having a good teacher — it never fails to provide the low-end information even though I have already moved on. So just like a good teacher isn’t presumptuous in what I’m supposed to know (which might force me to try and save face in case I do not, yet), information conveniently resurfaces.” – David Deutsch “When @haskellbook is done, it will be an unexpected mile- stone for #haskell. There will forever be Haskell before, and Haskell after.” – Jason Kuhrt “I feel safe recommending Haskell to beginners now that @haskellbook is available, which is very beginner friendly” – Gabriel Gonzalez “”Structure and Interpretation of Computer Programs” has its credit, but @haskellbook is now my #1 recommendation for FP beginners.” – Irio Musskopf “The book is long, but not slow — a large fraction of it is made up of examples and exercises. You can tell it’s written by someone who’s taught Haskell to programmers before.” – Christopher Jones

ii “I already have a lot of experience with Haskell, but I’ve never felt confident in it the way this book has made me feel.” – Alain O’Dea “Real deal with @haskellbook is that you don’t just learn Haskell; you get a hands on experience as to why functional programming works.” – George Makrydakis “One of my goals this year is to evangelize @haskellbook and @HaskellForMac. I think these tools will make anyone who uses them better. I want to get comfortable with it so that I can shift how I think about Swift.” – Janie Clayton

Contents Reader feedback . . . . . . . . . . . . . . . . . . . . . . . . . . i Contents iii Authors’ preface . . . . . . . . . . . . . . . . . . . . . . . . . . . xx Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . xxv Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxix Why This Book . . . . . . . . . . . . . . . . . . . . . . . . . . . xxix A few words to new programmers . . . . . . . . . . . . . . . xxxiv Haskevangelism . . . . . . . . . . . . . . . . . . . . . . . . . . . xxxv What’s in this book? . . . . . . . . . . . . . . . . . . . . . . . . xxxix Best practices for examples and exercises . . . . . . . . . . xliii 1 All You Need is Lambda 1 1.1 All You Need is Lambda . . . . . . . . . . . . . . . 2 1.2 What is functional programming? . . . . . . . . 2 1.3 What is a function? . . . . . . . . . . . . . . . . . . 4 1.4 The structure of lambda terms . . . . . . . . . . 7 1.5 Beta reduction . . . . . . . . . . . . . . . . . . . . . 10 1.6 Multiple arguments . . . . . . . . . . . . . . . . . . 15 1.7 Evaluation is simplification . . . . . . . . . . . . . 20 1.8 Combinators . . . . . . . . . . . . . . . . . . . . . . 21 iii

CONTENTS iv 1.9 Divergence . . . . . . . . . . . . . . . . . . . . . . . 23 1.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . 24 1.11 Chapter Exercises . . . . . . . . . . . . . . . . . . . 25 1.12 Answers . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.13 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 31 1.14 Follow-up resources . . . . . . . . . . . . . . . . . 33 2 Hello, Haskell! 34 2.1 Hello, Haskell . . . . . . . . . . . . . . . . . . . . . . 35 2.2 Interacting with Haskell code . . . . . . . . . . . 36 2.3 Understanding expressions . . . . . . . . . . . . . 40 2.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . 43 2.5 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 47 2.6 Infix operators . . . . . . . . . . . . . . . . . . . . . 50 2.7 Declaring values . . . . . . . . . . . . . . . . . . . . 57 2.8 Arithmetic functions in Haskell . . . . . . . . . . 67 2.9 Parenthesization . . . . . . . . . . . . . . . . . . . . 78 2.10 Let and where . . . . . . . . . . . . . . . . . . . . . 85 2.11 Chapter Exercises . . . . . . . . . . . . . . . . . . . 90 2.12 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 94 2.13 Follow-up resources . . . . . . . . . . . . . . . . . 96 3 Strings 97 3.1 Printing strings . . . . . . . . . . . . . . . . . . . . . 98 3.2 A first look at types . . . . . . . . . . . . . . . . . . 98 3.3 Printing simple strings . . . . . . . . . . . . . . . . 100

CONTENTS v 3.4 Top-level versus local definitions . . . . . . . . . 107 3.5 Types of concatenation functions . . . . . . . . . 110 3.6 Concatenation and scoping . . . . . . . . . . . . . 115 3.7 More list functions . . . . . . . . . . . . . . . . . . 119 3.8 Chapter Exercises . . . . . . . . . . . . . . . . . . . 122 3.9 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 128 4 Basic datatypes 131 4.1 Basic Datatypes . . . . . . . . . . . . . . . . . . . . 132 4.2 What are types? . . . . . . . . . . . . . . . . . . . . 133 4.3 Anatomy of a data declaration . . . . . . . . . . . 133 4.4 Numeric types . . . . . . . . . . . . . . . . . . . . . 137 4.5 Comparing values . . . . . . . . . . . . . . . . . . . 147 4.6 Go on and Bool me . . . . . . . . . . . . . . . . . . 152 4.7 Tuples . . . . . . . . . . . . . . . . . . . . . . . . . . 160 4.8 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 4.9 Chapter Exercises . . . . . . . . . . . . . . . . . . . 167 4.10 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 172 4.11 Names and variables . . . . . . . . . . . . . . . . . 175 5 Types 178 5.1 Types . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 5.2 What are types for? . . . . . . . . . . . . . . . . . . 180 5.3 How to read type signatures . . . . . . . . . . . . 182 5.4 Currying . . . . . . . . . . . . . . . . . . . . . . . . . 192 5.5 Polymorphism . . . . . . . . . . . . . . . . . . . . . 208

CONTENTS vi 5.6 Type inference . . . . . . . . . . . . . . . . . . . . . 217 5.7 Asserting types for declarations . . . . . . . . . . 222 5.8 Chapter Exercises . . . . . . . . . . . . . . . . . . . 225 5.9 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 239 5.10 Follow-up resources . . . . . . . . . . . . . . . . . 246 6 Typeclasses 247 6.1 Typeclasses . . . . . . . . . . . . . . . . . . . . . . . 248 6.2 What are typeclasses? . . . . . . . . . . . . . . . . . 248 6.3 Back to Bool . . . . . . . . . . . . . . . . . . . . . . 250 6.4 Eq . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 6.5 Writing typeclass instances . . . . . . . . . . . . . 257 6.6 Num . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 6.7 Type-defaulting typeclasses . . . . . . . . . . . . 278 6.8 Ord . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 6.9 Enum . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 6.10 Show . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 6.11 Read . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 6.12 Instances are dispatched by type . . . . . . . . . 304 6.13 Gimme more operations . . . . . . . . . . . . . . 309 6.14 Chapter Exercises . . . . . . . . . . . . . . . . . . . 314 6.15 Chapter Definitions . . . . . . . . . . . . . . . . . . 323 6.16 Typeclass inheritance, partial . . . . . . . . . . . 326 6.17 Follow-up resources . . . . . . . . . . . . . . . . . 326 7 More functional patterns 328

CONTENTS vii 7.1 Make it func-y . . . . . . . . . . . . . . . . . . . . . 329 7.2 Arguments and parameters . . . . . . . . . . . . . 329 7.3 Anonymous functions . . . . . . . . . . . . . . . . 339 7.4 Pattern matching . . . . . . . . . . . . . . . . . . . 344 7.5 Case expressions . . . . . . . . . . . . . . . . . . . . 360 7.6 Higher-order functions . . . . . . . . . . . . . . . 365 7.7 Guards . . . . . . . . . . . . . . . . . . . . . . . . . . 377 7.8 Function composition . . . . . . . . . . . . . . . . 387 7.9 Pointfree style . . . . . . . . . . . . . . . . . . . . . 392 7.10 Demonstrating composition . . . . . . . . . . . . 396 7.11 Chapter Exercises . . . . . . . . . . . . . . . . . . . 400 7.12 Chapter Definitions . . . . . . . . . . . . . . . . . . 406 7.13 Follow-up resources . . . . . . . . . . . . . . . . . 417 8 Recursion 419 8.1 Recursion . . . . . . . . . . . . . . . . . . . . . . . . 420 8.2 Factorial! . . . . . . . . . . . . . . . . . . . . . . . . . 421 8.3 Bottom . . . . . . . . . . . . . . . . . . . . . . . . . . 431 8.4 Fibonacci numbers . . . . . . . . . . . . . . . . . . 435 8.5 Integral division from scratch . . . . . . . . . . . 441 8.6 Chapter Exercises . . . . . . . . . . . . . . . . . . . 448 8.7 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 455 9 Lists 457 9.1 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458 9.2 The list datatype . . . . . . . . . . . . . . . . . . . . 458

CONTENTS viii 9.3 Pattern matching on lists . . . . . . . . . . . . . . 460 9.4 List’s syntactic sugar . . . . . . . . . . . . . . . . . 464 9.5 Using ranges to construct lists . . . . . . . . . . . 465 9.6 Extracting portions of lists . . . . . . . . . . . . . 469 9.7 List comprehensions . . . . . . . . . . . . . . . . . 477 9.8 Spines and nonstrict evaluation . . . . . . . . . . 485 9.9 Transforming lists of values . . . . . . . . . . . . 500 9.10 Filtering lists of values . . . . . . . . . . . . . . . . 511 9.11 Zipping lists . . . . . . . . . . . . . . . . . . . . . . . 513 9.12 Chapter Exercises . . . . . . . . . . . . . . . . . . . 517 9.13 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 526 9.14 Follow-up resources . . . . . . . . . . . . . . . . . 529 10 Folding lists 530 10.1 Folds . . . . . . . . . . . . . . . . . . . . . . . . . . . 531 10.2 Bringing you into the fold . . . . . . . . . . . . . . 531 10.3 Recursive patterns . . . . . . . . . . . . . . . . . . . 534 10.4 Fold right . . . . . . . . . . . . . . . . . . . . . . . . 535 10.5 Fold left . . . . . . . . . . . . . . . . . . . . . . . . . 548 10.6 How to write fold functions . . . . . . . . . . . . . 561 10.7 Folding and evaluation . . . . . . . . . . . . . . . . 568 10.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . 571 10.9 Scans . . . . . . . . . . . . . . . . . . . . . . . . . . . 573 10.10 Chapter Exercises . . . . . . . . . . . . . . . . . . . 578 10.11 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 585 10.12 Follow-up resources . . . . . . . . . . . . . . . . . 589

CONTENTS ix 11 Algebraic datatypes 590 11.1 Algebraic datatypes . . . . . . . . . . . . . . . . . . 591 11.2 Data declarations review . . . . . . . . . . . . . . . 592 11.3 Data and type constructors . . . . . . . . . . . . . 594 11.4 Type constructors and kinds . . . . . . . . . . . . 597 11.5 Data constructors and values . . . . . . . . . . . . 599 11.6 What’s a type and what’s data? . . . . . . . . . . . 605 11.7 Data constructor arities . . . . . . . . . . . . . . . 611 11.8 What makes these datatypes algebraic? . . . . . 614 11.9 newtype . . . . . . . . . . . . . . . . . . . . . . . . . 620 11.10 Sum types . . . . . . . . . . . . . . . . . . . . . . . . 627 11.11 Product types . . . . . . . . . . . . . . . . . . . . . . 631 11.12 Normal form . . . . . . . . . . . . . . . . . . . . . . 636 11.13 Constructing and deconstructing values . . . . 642 11.14 Function type is exponential . . . . . . . . . . . . 667 11.15 Higher-kinded datatypes . . . . . . . . . . . . . . 674 11.16 Lists are polymorphic . . . . . . . . . . . . . . . . 677 11.17 Binary Tree . . . . . . . . . . . . . . . . . . . . . . . 681 11.18 Chapter Exercises . . . . . . . . . . . . . . . . . . . 690 11.19 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 703 12 Signaling adversity 704 12.1 Signaling adversity . . . . . . . . . . . . . . . . . . 705 12.2 How I learned to stop worrying and love Nothing705 12.3 Bleating either . . . . . . . . . . . . . . . . . . . . . 709 12.4 Kinds, a thousand stars in your types . . . . . . 720

CONTENTS x 12.5 Chapter Exercises . . . . . . . . . . . . . . . . . . . 732 12.6 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 748 13 Building projects 750 13.1 Modules . . . . . . . . . . . . . . . . . . . . . . . . . 751 13.2 Making packages with Stack . . . . . . . . . . . . 753 13.3 Working with a basic project . . . . . . . . . . . . 754 13.4 Making our project a library . . . . . . . . . . . . 759 13.5 Module exports . . . . . . . . . . . . . . . . . . . . 762 13.6 More on importing modules . . . . . . . . . . . . 765 13.7 Making our program interactive . . . . . . . . . 773 13.8 do syntax and IO . . . . . . . . . . . . . . . . . . . . 779 13.9 Hangman game . . . . . . . . . . . . . . . . . . . . 784 13.10 Step One: Importing modules . . . . . . . . . . . 787 13.11 Step Two: Generating a word list . . . . . . . . . 793 13.12 Step Three: Making a puzzle . . . . . . . . . . . . 798 13.13 Adding a newtype . . . . . . . . . . . . . . . . . . . 810 13.14 Chapter exercises . . . . . . . . . . . . . . . . . . . 811 13.15 Follow-up resources . . . . . . . . . . . . . . . . . 815 14 Testing 817 14.1 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . 818 14.2 A quick tour of testing for the uninitiated . . . 819 14.3 Conventional testing . . . . . . . . . . . . . . . . . 821 14.4 Enter QuickCheck . . . . . . . . . . . . . . . . . . . 833 14.5 Morse code . . . . . . . . . . . . . . . . . . . . . . . 846

CONTENTS xi 14.6 Arbitrary instances . . . . . . . . . . . . . . . . . . 863 14.7 Chapter Exercises . . . . . . . . . . . . . . . . . . . 875 14.8 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 885 14.9 Follow-up resources . . . . . . . . . . . . . . . . . 886 15 Monoid, Semigroup 887 15.1 Monoids and semigroups . . . . . . . . . . . . . . 888 15.2 What we talk about when we talk about algebras889 15.3 Monoid . . . . . . . . . . . . . . . . . . . . . . . . . . 890 15.4 How Monoid is defined in Haskell . . . . . . . . 892 15.5 Examples of using Monoid . . . . . . . . . . . . . 893 15.6 Why Integer doesn’t have a Monoid . . . . . . . 895 15.7 Why bother? . . . . . . . . . . . . . . . . . . . . . . 901 15.8 Laws . . . . . . . . . . . . . . . . . . . . . . . . . . . . 903 15.9 Different instance, same representation . . . . . 908 15.10 Reusing algebras by asking for algebras . . . . . 911 15.11 Madness . . . . . . . . . . . . . . . . . . . . . . . . . 923 15.12 Better living through QuickCheck . . . . . . . . 925 15.13 Semigroup . . . . . . . . . . . . . . . . . . . . . . . . 936 15.14 Strength can be weakness . . . . . . . . . . . . . . 941 15.15 Chapter exercises . . . . . . . . . . . . . . . . . . . 944 15.16 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 955 15.17 Follow-up resources . . . . . . . . . . . . . . . . . 956 16 Functor 957 16.1 Functor . . . . . . . . . . . . . . . . . . . . . . . . . . 958

CONTENTS xii 16.2 What’s a functor? . . . . . . . . . . . . . . . . . . . 959 16.3 There’s a whole lot of fmap goin’ round . . . . . 962 16.4 Let’s talk about 𝑓 , baby . . . . . . . . . . . . . . . . 965 16.5 Functor Laws . . . . . . . . . . . . . . . . . . . . . . 979 16.6 The Good, the Bad, and the Ugly . . . . . . . . . 981 16.7 Commonly used functors . . . . . . . . . . . . . . 987 16.8 Transforming the unapplied type argument . . 1005 16.9 QuickChecking Functor instances . . . . . . . . 1010 16.10 Exercises: Instances of Func . . . . . . . . . . . . 1014 16.11 Ignoring possibilities . . . . . . . . . . . . . . . . . 1015 16.12 A somewhat surprising functor . . . . . . . . . . 1024 16.13 More structure, more functors . . . . . . . . . . . 1028 16.14 IO Functor . . . . . . . . . . . . . . . . . . . . . . . . 1030 16.15 What if we want to do something different? . . 1034 16.16 Functors are unique to a datatype . . . . . . . . . 1039 16.17 Chapter exercises . . . . . . . . . . . . . . . . . . . 1041 16.18 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 1046 16.19 Follow-up resources . . . . . . . . . . . . . . . . . 1050 17 Applicative 1052 17.1 Applicative . . . . . . . . . . . . . . . . . . . . . . . 1053 17.2 Defining Applicative . . . . . . . . . . . . . . . . . 1054 17.3 Functor vs. Applicative . . . . . . . . . . . . . . . . 1057 17.4 Applicative functors are monoidal functors . . 1059 17.5 Applicative in use . . . . . . . . . . . . . . . . . . . 1067 17.6 Applicative laws . . . . . . . . . . . . . . . . . . . . 1106

CONTENTS xiii 17.7 You knew this was coming . . . . . . . . . . . . . 1115 17.8 ZipList Monoid . . . . . . . . . . . . . . . . . . . . 1120 17.9 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1135 17.10 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 1138 17.11 Follow-up resources . . . . . . . . . . . . . . . . . 1138 18 Monad 1140 18.1 Monad . . . . . . . . . . . . . . . . . . . . . . . . . . 1141 18.2 Sorry — a monad is not a burrito . . . . . . . . . 1141 18.3 Do syntax and monads . . . . . . . . . . . . . . . . 1154 18.4 Examples of Monad use . . . . . . . . . . . . . . . . 1163 18.5 Monad laws . . . . . . . . . . . . . . . . . . . . . . . 1188 18.6 Application and composition . . . . . . . . . . . 1199 18.7 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1206 18.8 Definition . . . . . . . . . . . . . . . . . . . . . . . . 1209 18.9 Follow-up resources . . . . . . . . . . . . . . . . . 1211 19 Applying structure 1212 19.1 Applied structure . . . . . . . . . . . . . . . . . . . 1213 19.2 Monoid . . . . . . . . . . . . . . . . . . . . . . . . . . . 1213 19.3 Functor . . . . . . . . . . . . . . . . . . . . . . . . . . 1221 19.4 Applicative . . . . . . . . . . . . . . . . . . . . . . . . 1226 19.5 Monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1233 19.6 An end-to-end example: URL shortener . . . . 1237 19.7 That’s a wrap! . . . . . . . . . . . . . . . . . . . . . . 1257 19.8 Follow-up resources . . . . . . . . . . . . . . . . . 1258

CONTENTS xiv 20 Foldable 1259 20.1 Foldable . . . . . . . . . . . . . . . . . . . . . . . . . 1260 20.2 The Foldable class . . . . . . . . . . . . . . . . . . . 1261 20.3 Revenge of the monoids . . . . . . . . . . . . . . . 1262 20.4 Demonstrating Foldable instances . . . . . . . . . 1268 20.5 Some basic derived operations . . . . . . . . . . 1273 20.6 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1280 20.7 Follow-up resources . . . . . . . . . . . . . . . . . 1281 21 Traversable 1282 21.1 Traversable . . . . . . . . . . . . . . . . . . . . . . . 1283 21.2 The Traversable typeclass definition . . . . . . . 1284 21.3 sequenceA . . . . . . . . . . . . . . . . . . . . . . . . . 1285 21.4 traverse . . . . . . . . . . . . . . . . . . . . . . . . . . 1287 21.5 So, what’s Traversable for? . . . . . . . . . . . . . . 1291 21.6 Morse code revisited . . . . . . . . . . . . . . . . . 1292 21.7 Axing tedious code . . . . . . . . . . . . . . . . . . 1296 21.8 Do all the things . . . . . . . . . . . . . . . . . . . . 1300 21.9 Traversable instances . . . . . . . . . . . . . . . . . 1304 21.10 Traversable Laws . . . . . . . . . . . . . . . . . . . . 1307 21.11 Quality Control . . . . . . . . . . . . . . . . . . . . 1308 21.12 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1309 21.13 Follow-up resources . . . . . . . . . . . . . . . . . 1314 22 Reader 1315 22.1 Reader . . . . . . . . . . . . . . . . . . . . . . . . . . 1316

CONTENTS xv 22.2 A new beginning . . . . . . . . . . . . . . . . . . . . 1317 22.3 This is Reader . . . . . . . . . . . . . . . . . . . . . 1327 22.4 Breaking down the Functor of functions . . . . . 1328 22.5 But uh, Reader? . . . . . . . . . . . . . . . . . . . . . 1334 22.6 Functions have an Applicative too . . . . . . . . . 1337 22.7 The Monad of functions . . . . . . . . . . . . . . . . 1345 22.8 Reader Monad by itself is boring . . . . . . . . . . . 1351 22.9 You can change what comes below, but not above1354 22.10 You tend to see ReaderT, not Reader . . . . . . . . . 1355 22.11 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1355 22.12 Definition . . . . . . . . . . . . . . . . . . . . . . . . 1362 22.13 Follow-up resources . . . . . . . . . . . . . . . . . 1363 23 State 1364 23.1 State . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1365 23.2 What is state? . . . . . . . . . . . . . . . . . . . . . . 1365 23.3 Random numbers . . . . . . . . . . . . . . . . . . . 1367 23.4 The State newtype . . . . . . . . . . . . . . . . . . . 1371 23.5 Throw down . . . . . . . . . . . . . . . . . . . . . . 1374 23.6 Write State for yourself . . . . . . . . . . . . . . . 1383 23.7 Get a coding job with one weird trick . . . . . . 1385 23.8 Chapter exercises . . . . . . . . . . . . . . . . . . . 1392 23.9 Follow-up resources . . . . . . . . . . . . . . . . . 1394 24 Parser combinators 1395 24.1 Parser combinators . . . . . . . . . . . . . . . . . . 1396

CONTENTS xvi 24.2 A few more words of introduction . . . . . . . . 1398 24.3 Understanding the parsing process . . . . . . . . 1399 24.4 Parsing fractions . . . . . . . . . . . . . . . . . . . . 1416 24.5 Haskell’s parsing ecosystem . . . . . . . . . . . . . 1425 24.6 Alternative . . . . . . . . . . . . . . . . . . . . . . . . 1429 24.7 Parsing configuration files . . . . . . . . . . . . . . 1444 24.8 Character and token parsers . . . . . . . . . . . . 1460 24.9 Polymorphic parsers . . . . . . . . . . . . . . . . . 1465 24.10 Marshalling from an AST to a datatype . . . . . 1474 24.11 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1491 24.12 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 1500 24.13 Follow-up resources . . . . . . . . . . . . . . . . . 1501 25 Composing types 1504 25.1 Composing types . . . . . . . . . . . . . . . . . . . 1505 25.2 Common functions as types . . . . . . . . . . . . 1506 25.3 Two little functors sittin’ in a tree, L-I-F-T-I-N-G . . . . . . . . . . . . . . . . . . . . . 1511 25.4 Twinplicative . . . . . . . . . . . . . . . . . . . . . . 1514 25.5 Twonad? . . . . . . . . . . . . . . . . . . . . . . . . . 1516 25.6 Exercises: Compose Instances . . . . . . . . . . . 1518 25.7 Monad transformers . . . . . . . . . . . . . . . . . 1520 25.8 IdentityT . . . . . . . . . . . . . . . . . . . . . . . . . 1523 25.9 Finding a pattern . . . . . . . . . . . . . . . . . . . 1542 26 Monad transformers 1546

CONTENTS xvii 26.1 Monad transformers . . . . . . . . . . . . . . . . . 1547 26.2 MaybeT . . . . . . . . . . . . . . . . . . . . . . . . . . 1547 26.3 EitherT . . . . . . . . . . . . . . . . . . . . . . . . . . 1555 26.4 ReaderT . . . . . . . . . . . . . . . . . . . . . . . . . 1557 26.5 StateT . . . . . . . . . . . . . . . . . . . . . . . . . . . 1561 26.6 Types you probably don’t want to use . . . . . . 1566 26.7 Recovering an ordinary type from a transformer1568 26.8 Lexically inner is structurally outer . . . . . . . 1570 26.9 MonadTrans . . . . . . . . . . . . . . . . . . . . . . 1574 26.10 MonadIO aka zoom-zoom . . . . . . . . . . . . . 1597 26.11 Monad transformers in use . . . . . . . . . . . . . 1601 26.12 Monads do not commute . . . . . . . . . . . . . . 1617 26.13 Transform if you want to . . . . . . . . . . . . . . 1617 26.14 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1618 26.15 Defintion . . . . . . . . . . . . . . . . . . . . . . . . . 1627 26.16 Follow-up resources . . . . . . . . . . . . . . . . . 1628 27 Nonstrictness 1629 27.1 Laziness . . . . . . . . . . . . . . . . . . . . . . . . . 1630 27.2 Observational Bottom Theory . . . . . . . . . . . 1631 27.3 Outside in, inside out . . . . . . . . . . . . . . . . . 1633 27.4 What does the other way look like? . . . . . . . . 1637 27.5 Can we make Haskell strict? . . . . . . . . . . . . . 1638 27.6 Call by name, call by need . . . . . . . . . . . . . 1657 27.7 Nonstrict evaluation changes what we can do . 1658 27.8 Thunk Life . . . . . . . . . . . . . . . . . . . . . . . 1660

CONTENTS xviii 27.9 Sharing is caring . . . . . . . . . . . . . . . . . . . . 1664 27.10 Refutable and irrefutable patterns . . . . . . . . 1686 27.11 Bang patterns . . . . . . . . . . . . . . . . . . . . . . 1689 27.12 Strict and StrictData . . . . . . . . . . . . . . . . . 1693 27.13 Adding strictness . . . . . . . . . . . . . . . . . . . . 1695 27.14 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1702 27.15 Follow-up resources . . . . . . . . . . . . . . . . . 1705 28 Basic libraries 1707 28.1 Basic libraries and data structures . . . . . . . . . 1708 28.2 Benchmarking with Criterion . . . . . . . . . . . 1709 28.3 Profiling your programs . . . . . . . . . . . . . . . 1727 28.4 Constant applicative forms . . . . . . . . . . . . . 1732 28.5 Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1737 28.6 Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1741 28.7 Sequence . . . . . . . . . . . . . . . . . . . . . . . . . 1744 28.8 Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . 1748 28.9 String types . . . . . . . . . . . . . . . . . . . . . . . 1762 28.10 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1775 28.11 Follow-up resources . . . . . . . . . . . . . . . . . 1779 29 IO 1781 29.1 IO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1782 29.2 Where IO explanations go astray . . . . . . . . . 1783 29.3 The reason we need this type . . . . . . . . . . . 1786 29.4 Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . 1788

CONTENTS xix 29.5 IO doesn’t disable sharing for everything . . . . 1795 29.6 Purity is losing meaning . . . . . . . . . . . . . . . 1797 29.7 IO’s Functor, Applicative, and Monad . . . . . . 1800 29.8 Well, then, how do we MVar? . . . . . . . . . . . . 1806 29.9 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1809 29.10 Follow-up resources . . . . . . . . . . . . . . . . . 1810 30 When things go wrong 1812 30.1 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . 1813 30.2 The Exception class and methods . . . . . . . . . 1814 30.3 This machine kills programs . . . . . . . . . . . . 1825 30.4 Want either? Try! . . . . . . . . . . . . . . . . . . . 1832 30.5 The unbearable imprecision of trying . . . . . . 1837 30.6 Why throwIO? . . . . . . . . . . . . . . . . . . . . . 1840 30.7 Making our own exception types . . . . . . . . . 1844 30.8 Surprising interaction with bottom . . . . . . . . 1851 30.9 Asynchronous Exceptions . . . . . . . . . . . . . . 1853 30.10 Follow-up Reading . . . . . . . . . . . . . . . . . . 1857 31 Final project 1859 31.1 Final project . . . . . . . . . . . . . . . . . . . . . . . 1860 31.2 fingerd . . . . . . . . . . . . . . . . . . . . . . . . . . 1860 31.3 Exploring finger . . . . . . . . . . . . . . . . . . . . 1862 31.4 Slightly modernized fingerd . . . . . . . . . . . . 1872 31.5 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1887