Haskell Programming from First Principles

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