Haskell Programming from First Principles

Description

Reader feedback......Page 2 Contents......Page 3 Authors' preface......Page 15 Acknowledgements......Page 18 Why This Book......Page 21 A few words to new programmers......Page 24 Haskevangelism......Page 25 What's in this book?......Page 27 Best practices for examples and exercises......Page 30 All You Need is Lambda......Page 33 What is functional programming?......Page 34 What is a function?......Page 35 The structure of lambda terms......Page 37 Beta reduction......Page 39 Multiple arguments......Page 42 Combinators......Page 46 Divergence......Page 47 Summary......Page 48 Chapter Exercises......Page 49 Answers......Page 51 Definitions......Page 54 Follow-up resources......Page 55 Hello, Haskell!......Page 56 Interacting with Haskell code......Page 57 Understanding expressions......Page 60 Functions......Page 62 Evaluation......Page 65 Infix operators......Page 67 Declaring values......Page 71 Arithmetic functions in Haskell......Page 77 Parenthesization......Page 84 Let and where......Page 89 Chapter Exercises......Page 92 Definitions......Page 95 Follow-up resources......Page 96 Strings......Page 97 A first look at types......Page 98 Printing simple strings......Page 99 Top-level versus local definitions......Page 104 Types of concatenation functions......Page 106 Concatenation and scoping......Page 108 More list functions......Page 111 Chapter Exercises......Page 113 Definitions......Page 117 Basic datatypes......Page 118 Anatomy of a data declaration......Page 119 Numeric types......Page 122 Comparing values......Page 128 Go on and Bool me......Page 131 Tuples......Page 137 Lists......Page 140 Chapter Exercises......Page 141 Definitions......Page 145 Names and variables......Page 147 Types......Page 149 What are types for?......Page 150 How to read type signatures......Page 152 Currying......Page 158 Polymorphism......Page 169 Type inference......Page 174 Asserting types for declarations......Page 178 Chapter Exercises......Page 179 Definitions......Page 189 Follow-up resources......Page 193 Typeclasses......Page 194 What are typeclasses?......Page 195 Back to Bool......Page 196 Eq......Page 197 Writing typeclass instances......Page 201 Num......Page 211 Type-defaulting typeclasses......Page 214 Ord......Page 218 Enum......Page 225 Show......Page 226 Instances are dispatched by type......Page 231 Gimme more operations......Page 235 Chapter Exercises......Page 238 Chapter Definitions......Page 243 Follow-up resources......Page 246 More functional patterns......Page 247 Arguments and parameters......Page 248 Anonymous functions......Page 255 Pattern matching......Page 258 Case expressions......Page 268 Higher-order functions......Page 271 Guards......Page 279 Function composition......Page 285 Pointfree style......Page 289 Demonstrating composition......Page 291 Chapter Exercises......Page 294 Chapter Definitions......Page 298 Follow-up resources......Page 306 Recursion......Page 307 Recursion......Page 308 Factorial!......Page 309 Bottom......Page 315 Fibonacci numbers......Page 318 Integral division from scratch......Page 321 Chapter Exercises......Page 326 Definitions......Page 330 Lists......Page 332 The list datatype......Page 333 Pattern matching on lists......Page 334 List's syntactic sugar......Page 336 Using ranges to construct lists......Page 337 Extracting portions of lists......Page 340 List comprehensions......Page 344 Spines and nonstrict evaluation......Page 350 Transforming lists of values......Page 359 Filtering lists of values......Page 366 Zipping lists......Page 368 Chapter Exercises......Page 371 Definitions......Page 377 Follow-up resources......Page 379 Folding lists......Page 380 Bringing you into the fold......Page 381 Recursive patterns......Page 383 Fold right......Page 384 Fold left......Page 392 How to write fold functions......Page 400 Folding and evaluation......Page 405 Summary......Page 407 Scans......Page 408 Chapter Exercises......Page 411 Definitions......Page 416 Follow-up resources......Page 418 Algebraic datatypes......Page 419 Data declarations review......Page 420 Data and type constructors......Page 422 Type constructors and kinds......Page 424 Data constructors and values......Page 425 What's a type and what's data?......Page 429 Data constructor arities......Page 432 What makes these datatypes algebraic?......Page 435 newtype......Page 438 Sum types......Page 443 Product types......Page 446 Normal form......Page 449 Constructing and deconstructing values......Page 453 Function type is exponential......Page 467 Higher-kinded datatypes......Page 473 Lists are polymorphic......Page 475 Binary Tree......Page 478 Chapter Exercises......Page 484 Definitions......Page 492 Signaling adversity......Page 493 How I learned to stop worrying and love Nothing......Page 494 Bleating either......Page 497 Kinds, a thousand stars in your types......Page 503 Chapter Exercises......Page 512 Definitions......Page 523 Building projects......Page 524 Modules......Page 525 Making packages with Stack......Page 526 Working with a basic project......Page 527 Making our project a library......Page 530 Module exports......Page 532 More on importing modules......Page 534 Making our program interactive......Page 539 do syntax and IO......Page 542 Hangman game......Page 546 Step One: Importing modules......Page 548 Step Two: Generating a word list......Page 551 Step Three: Making a puzzle......Page 554 Adding a newtype......Page 562 Chapter exercises......Page 563 Follow-up resources......Page 566 Testing......Page 567 A quick tour of testing for the uninitiated......Page 568 Conventional testing......Page 570 Enter QuickCheck......Page 577 Morse code......Page 586 Arbitrary instances......Page 597 Chapter Exercises......Page 605 Definitions......Page 611 Follow-up resources......Page 612 Monoid, Semigroup......Page 613 What we talk about when we talk about algebras......Page 614 Monoid......Page 615 How Monoid is defined in Haskell......Page 616 Examples of using Monoid......Page 617 Why Integer doesn't have a Monoid......Page 618 Why bother?......Page 622 Laws......Page 623 Different instance, same representation......Page 626 Reusing algebras by asking for algebras......Page 628 Madness......Page 636 Better living through QuickCheck......Page 637 Semigroup......Page 644 Strength can be weakness......Page 647 Chapter exercises......Page 649 Definitions......Page 656 Follow-up resources......Page 657 Functor......Page 658 Functor......Page 659 What's a functor?......Page 660 There's a whole lot of fmap goin' round......Page 661 Let's talk about f, baby......Page 663 Functor Laws......Page 672 The Good, the Bad, and the Ugly......Page 673 Commonly used functors......Page 677 Transforming the unapplied type argument......Page 689 QuickChecking Functor instances......Page 692 Ignoring possibilities......Page 695 A somewhat surprising functor......Page 701 More structure, more functors......Page 704 IO Functor......Page 705 What if we want to do something different?......Page 707 Functors are unique to a datatype......Page 710 Chapter exercises......Page 711 Definitions......Page 715 Follow-up resources......Page 717 Applicative......Page 718 Defining Applicative......Page 719 Functor vs. Applicative......Page 721 Applicative functors are monoidal functors......Page 723 Applicative in use......Page 728 Applicative laws......Page 753 You knew this was coming......Page 759 ZipList Monoid......Page 762 Chapter Exercises......Page 773 Definitions......Page 774 Follow-up resources......Page 775 Monad......Page 776 Sorry — a monad is not a burrito......Page 777 Do syntax and monads......Page 785 Examples of Monad use......Page 791 Monad laws......Page 808 Application and composition......Page 815 Chapter Exercises......Page 820 Definition......Page 821 Follow-up resources......Page 823 Applying structure......Page 824 Monoid......Page 825 Functor......Page 830 Applicative......Page 833 Monad......Page 838 An end-to-end example: URL shortener......Page 839 That's a wrap!......Page 852 Follow-up resources......Page 853 Foldable......Page 854 The Foldable class......Page 855 Revenge of the monoids......Page 856 Demonstrating Foldable instances......Page 860 Some basic derived operations......Page 863 Chapter Exercises......Page 868 Follow-up resources......Page 869 Traversable......Page 870 The Traversable typeclass definition......Page 871 sequenceA......Page 872 traverse......Page 874 So, what's Traversable for?......Page 876 Morse code revisited......Page 877 Axing tedious code......Page 880 Do all the things......Page 882 Traversable instances......Page 884 Traversable Laws......Page 886 Quality Control......Page 887 Chapter Exercises......Page 888 Follow-up resources......Page 891 Reader......Page 892 A new beginning......Page 893 This is Reader......Page 900 Breaking down the Functor of functions......Page 901 But uh, Reader?......Page 903 Functions have an Applicative too......Page 905 The Monad of functions......Page 910 Reader Monad by itself is boring......Page 914 You tend to see ReaderT, not Reader......Page 916 Chapter Exercises......Page 917 Definition......Page 921 Follow-up resources......Page 922 State......Page 923 What is state?......Page 924 Random numbers......Page 925 The State newtype......Page 928 Throw down......Page 930 Write State for yourself......Page 935 Get a coding job with one weird trick......Page 937 Chapter exercises......Page 941 Follow-up resources......Page 942 Parser combinators......Page 943 Parser combinators......Page 944 Understanding the parsing process......Page 945 Parsing fractions......Page 956 Haskell's parsing ecosystem......Page 962 Alternative......Page 965 Parsing configuration files......Page 975 Character and token parsers......Page 986 Polymorphic parsers......Page 989 Marshalling from an AST to a datatype......Page 995 Chapter Exercises......Page 1006 Follow-up resources......Page 1012 Composing types......Page 1014 Composing types......Page 1015 Common functions as types......Page 1016 Two little functors sittin' in a tree, L-I-F-T-I-N-G......Page 1018 Twonad?......Page 1021 Exercises: Compose Instances......Page 1023 Monad transformers......Page 1025 IdentityT......Page 1026 Finding a pattern......Page 1038 Monad transformers......Page 1041 MaybeT......Page 1042 EitherT......Page 1047 ReaderT......Page 1048 StateT......Page 1050 Types you probably don't want to use......Page 1053 Recovering an ordinary type from a transformer......Page 1055 Lexically inner is structurally outer......Page 1056 MonadTrans......Page 1059 MonadIO aka zoom-zoom......Page 1072 Monad transformers in use......Page 1075 Monads do not commute......Page 1084 Chapter Exercises......Page 1085 Defintion......Page 1091 Follow-up resources......Page 1092 Nonstrictness......Page 1093 Laziness......Page 1094 Observational Bottom Theory......Page 1095 Outside in, inside out......Page 1096 What does the other way look like?......Page 1098 Can we make Haskell strict?......Page 1099 Call by name, call by need......Page 1111 Nonstrict evaluation changes what we can do......Page 1112 Thunk Life......Page 1113 Sharing is caring......Page 1116 Refutable and irrefutable patterns......Page 1130 Bang patterns......Page 1132 Strict and StrictData......Page 1135 Adding strictness......Page 1136 Chapter Exercises......Page 1141 Follow-up resources......Page 1143 Basic libraries......Page 1144 Benchmarking with Criterion......Page 1145 Profiling your programs......Page 1157 Constant applicative forms......Page 1160 Map......Page 1164 Set......Page 1166 Sequence......Page 1168 Vector......Page 1170 String types......Page 1180 Chapter Exercises......Page 1188 Follow-up resources......Page 1190 IO......Page 1192 IO......Page 1193 Where IO explanations go astray......Page 1194 The reason we need this type......Page 1196 Sharing......Page 1197 IO doesn't disable sharing for everything......Page 1201 Purity is losing meaning......Page 1203 IO's Functor, Applicative, and Monad......Page 1204 Well, then, how do we MVar?......Page 1208 Chapter Exercises......Page 1210 Follow-up resources......Page 1211 When things go wrong......Page 1212 The Exception class and methods......Page 1213 This machine kills programs......Page 1220 Want either? Try!......Page 1225 The unbearable imprecision of trying......Page 1229 Why throwIO?......Page 1231 Making our own exception types......Page 1233 Surprising interaction with bottom......Page 1237 Asynchronous Exceptions......Page 1239 Follow-up Reading......Page 1242 Final project......Page 1243 fingerd......Page 1244 Exploring finger......Page 1245 Slightly modernized fingerd......Page 1252 Chapter Exercises......Page 1262