《Haskell Full Programming From First Principles》

【实例截图】

【核心代码】

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 . . . . . . . . . . 6
1.5 Beta reduction . . . . . . . . . . . . . . . . . . . . . 9
1.6 Multiple arguments . . . . . . . . . . . . . . . . . . 14
1.7 Evaluation is simplification . . . . . . . . . . . . . 20
1.8 Combinators . . . . . . . . . . . . . . . . . . . . . . 21
iii
CONTENTS iv
1.9 Divergence . . . . . . . . . . . . . . . . . . . . . . . 22
1.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . 23
1.11 Chapter Exercises . . . . . . . . . . . . . . . . . . . 24
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 . . . . . . . . . . . . . . . . . . . . . 51
2.7 Declaring values . . . . . . . . . . . . . . . . . . . . 57
2.8 Arithmetic functions in Haskell . . . . . . . . . . 68
2.9 Parenthesization . . . . . . . . . . . . . . . . . . . . 78
2.10 Let and where . . . . . . . . . . . . . . . . . . . . . 85
2.11 Chapter Exercises . . . . . . . . . . . . . . . . . . . 89
2.12 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 94
2.13 Follow-up resources . . . . . . . . . . . . . . . . . 96
3 Strings 98
3.1 Printing strings . . . . . . . . . . . . . . . . . . . . . 99
3.2 A first look at types . . . . . . . . . . . . . . . . . . 99
3.3 Printing simple strings . . . . . . . . . . . . . . . . 101
CONTENTS v
3.4 Top-level versus local definitions . . . . . . . . . 108
3.5 Types of concatenation functions . . . . . . . . . 111
3.6 Concatenation and scoping . . . . . . . . . . . . . 116
3.7 More list functions . . . . . . . . . . . . . . . . . . 119
3.8 Chapter Exercises . . . . . . . . . . . . . . . . . . . 122
3.9 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 128
4 Basic datatypes 130
4.1 Basic Datatypes . . . . . . . . . . . . . . . . . . . . 131
4.2 What are types? . . . . . . . . . . . . . . . . . . . . 132
4.3 Anatomy of a data declaration . . . . . . . . . . . 132
4.4 Numeric types . . . . . . . . . . . . . . . . . . . . . 136
4.5 Comparing values . . . . . . . . . . . . . . . . . . . 145
4.6 Go on and Bool me . . . . . . . . . . . . . . . . . . 150
4.7 Tuples . . . . . . . . . . . . . . . . . . . . . . . . . . 159
4.8 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
4.9 Chapter Exercises . . . . . . . . . . . . . . . . . . . 165
4.10 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 170
4.11 Names and variables . . . . . . . . . . . . . . . . . 173
5 Types 176
5.1 Types . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
5.2 What are types for? . . . . . . . . . . . . . . . . . . 178
5.3 How to read type signatures . . . . . . . . . . . . 180
5.4 Currying . . . . . . . . . . . . . . . . . . . . . . . . . 190
5.5 Polymorphism . . . . . . . . . . . . . . . . . . . . . 206
CONTENTS vi
5.6 Type inference . . . . . . . . . . . . . . . . . . . . . 215
5.7 Asserting types for declarations . . . . . . . . . . 220
5.8 Chapter Exercises . . . . . . . . . . . . . . . . . . . 223
5.9 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 237
5.10 Follow-up resources . . . . . . . . . . . . . . . . . 244
6 Typeclasses 245
6.1 Typeclasses . . . . . . . . . . . . . . . . . . . . . . . 246
6.2 What are typeclasses? . . . . . . . . . . . . . . . . . 246
6.3 Back to Bool . . . . . . . . . . . . . . . . . . . . . . 248
6.4 Eq . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
6.5 Writing typeclass instances . . . . . . . . . . . . . 255
6.6 Num . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
6.7 Type-defaulting typeclasses . . . . . . . . . . . . 276
6.8 Ord . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
6.9 Enum . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
6.10 Show . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
6.11 Read . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
6.12 Instances are dispatched by type . . . . . . . . . 302
6.13 Gimme more operations . . . . . . . . . . . . . . 307
6.14 Chapter Exercises . . . . . . . . . . . . . . . . . . . 312
6.15 Chapter Definitions . . . . . . . . . . . . . . . . . . 321
6.16 Typeclass inheritance, partial . . . . . . . . . . . 324
6.17 Follow-up resources . . . . . . . . . . . . . . . . . 324
7 More functional patterns 326
CONTENTS vii
7.1 Make it func-y . . . . . . . . . . . . . . . . . . . . . 327
7.2 Arguments and parameters . . . . . . . . . . . . . 327
7.3 Anonymous functions . . . . . . . . . . . . . . . . 337
7.4 Pattern matching . . . . . . . . . . . . . . . . . . . 342
7.5 Case expressions . . . . . . . . . . . . . . . . . . . . 356
7.6 Higher-order functions . . . . . . . . . . . . . . . 360
7.7 Guards . . . . . . . . . . . . . . . . . . . . . . . . . . 373
7.8 Function composition . . . . . . . . . . . . . . . . 382
7.9 Pointfree style . . . . . . . . . . . . . . . . . . . . . 388
7.10 Demonstrating composition . . . . . . . . . . . . 392
7.11 Chapter Exercises . . . . . . . . . . . . . . . . . . . 396
7.12 Chapter Definitions . . . . . . . . . . . . . . . . . . 401
7.13 Follow-up resources . . . . . . . . . . . . . . . . . 411
8 Recursion 413
8.1 Recursion . . . . . . . . . . . . . . . . . . . . . . . . 414
8.2 Factorial . . . . . . . . . . . . . . . . . . . . . . . . . 415
8.3 Bottom . . . . . . . . . . . . . . . . . . . . . . . . . . 425
8.4 Fibonacci numbers . . . . . . . . . . . . . . . . . . 429
8.5 Integral division from scratch . . . . . . . . . . . 435
8.6 Chapter Exercises . . . . . . . . . . . . . . . . . . . 442
8.7 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 449
9 Lists 450
9.1 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
9.2 The list datatype . . . . . . . . . . . . . . . . . . . . 451
CONTENTS viii
9.3 Pattern matching on lists . . . . . . . . . . . . . . 453
9.4 List’s syntactic sugar . . . . . . . . . . . . . . . . . 456
9.5 Using ranges to construct lists . . . . . . . . . . . 458
9.6 Extracting portions of lists . . . . . . . . . . . . . 461
9.7 List comprehensions . . . . . . . . . . . . . . . . . 468
9.8 Spines and nonstrict evaluation . . . . . . . . . . 475
9.9 Transforming lists of values . . . . . . . . . . . . 490
9.10 Filtering lists of values . . . . . . . . . . . . . . . . 501
9.11 Zipping lists . . . . . . . . . . . . . . . . . . . . . . . 503
9.12 Chapter Exercises . . . . . . . . . . . . . . . . . . . 507
9.13 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 516
9.14 Follow-up resources . . . . . . . . . . . . . . . . . 519
10 Folding lists 520
10.1 Folds . . . . . . . . . . . . . . . . . . . . . . . . . . . 521
10.2 Bringing you into the fold . . . . . . . . . . . . . . 521
10.3 Recursive patterns . . . . . . . . . . . . . . . . . . . 523
10.4 Fold right . . . . . . . . . . . . . . . . . . . . . . . . 525
10.5 Fold left . . . . . . . . . . . . . . . . . . . . . . . . . 537
10.6 How to write fold functions . . . . . . . . . . . . . 550
10.7 Folding and evaluation . . . . . . . . . . . . . . . . 557
10.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . 559
10.9 Scans . . . . . . . . . . . . . . . . . . . . . . . . . . . 561
10.10 Chapter Exercises . . . . . . . . . . . . . . . . . . . 566
10.11 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 572
10.12 Follow-up resources . . . . . . . . . . . . . . . . . 575
CONTENTS ix
11 Algebraic datatypes 576
11.1 Algebraic datatypes . . . . . . . . . . . . . . . . . . 577
11.2 Data declarations review . . . . . . . . . . . . . . . 578
11.3 Data and type constructors . . . . . . . . . . . . . 580
11.4 Type constructors and kinds . . . . . . . . . . . . 583
11.5 Data constructors and values . . . . . . . . . . . . 585
11.6 What’s a type and what’s data? . . . . . . . . . . . 591
11.7 Data constructor arities . . . . . . . . . . . . . . . 597
11.8 What makes these datatypes algebraic? . . . . . 601
11.9 newtype . . . . . . . . . . . . . . . . . . . . . . . . . 607
11.10 Sum types . . . . . . . . . . . . . . . . . . . . . . . . 614
11.11 Product types . . . . . . . . . . . . . . . . . . . . . . 618
11.12 Normal form . . . . . . . . . . . . . . . . . . . . . . 623
11.13 Constructing and deconstructing values . . . . 629
11.14 Function type is exponential . . . . . . . . . . . . 652
11.15 Higher-kinded datatypes . . . . . . . . . . . . . . 660
11.16 Lists are polymorphic . . . . . . . . . . . . . . . . 663
11.17 Binary Tree . . . . . . . . . . . . . . . . . . . . . . . 668
11.18 Chapter Exercises . . . . . . . . . . . . . . . . . . . 676
11.19 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 688
12 Signaling adversity 689
12.1 Signaling adversity . . . . . . . . . . . . . . . . . . 690
12.2 How I learned to stop worrying and love Nothing 690
12.3 Bleating either . . . . . . . . . . . . . . . . . . . . . 694
12.4 Kinds, a thousand stars in your types . . . . . . 704
CONTENTS x
12.5 Chapter Exercises . . . . . . . . . . . . . . . . . . . 716
12.6 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 732
13 Building projects 733
13.1 Modules . . . . . . . . . . . . . . . . . . . . . . . . . 734
13.2 Making packages with Stack . . . . . . . . . . . . 736
13.3 Working with a basic project . . . . . . . . . . . . 737
13.4 Making our project a library . . . . . . . . . . . . 742
13.5 Module exports . . . . . . . . . . . . . . . . . . . . 745
13.6 More on importing modules . . . . . . . . . . . . 748
13.7 Making our program interactive . . . . . . . . . 756
13.8 do syntax and IO . . . . . . . . . . . . . . . . . . . . 761
13.9 Hangman game . . . . . . . . . . . . . . . . . . . . 766
13.10 Step One: Importing modules . . . . . . . . . . . 770
13.11 Step Two: Generating a word list . . . . . . . . . 776
13.12 Step Three: Making a puzzle . . . . . . . . . . . . 780
13.13 Adding a newtype . . . . . . . . . . . . . . . . . . . 792
13.14 Chapter exercises . . . . . . . . . . . . . . . . . . . 793
13.15 Follow-up resources . . . . . . . . . . . . . . . . . 797
14 Testing 799
14.1 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . 800
14.2 A quick tour of testing for the uninitiated . . . 801
14.3 Conventional testing . . . . . . . . . . . . . . . . . 803
14.4 Enter QuickCheck . . . . . . . . . . . . . . . . . . . 815
14.5 Morse code . . . . . . . . . . . . . . . . . . . . . . . 828
CONTENTS xi
14.6 Kicking around QuickCheck . . . . . . . . . . . . 845
14.7 Chapter Exercises . . . . . . . . . . . . . . . . . . . 857
14.8 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 867
14.9 Follow-up resources . . . . . . . . . . . . . . . . . 868
15 Monoid, Semigroup 869
15.1 Monoids and semigroups . . . . . . . . . . . . . . 870
15.2 What we talk about when we talk about algebras 871
15.3 Monoid . . . . . . . . . . . . . . . . . . . . . . . . . . 872
15.4 How Monoid is defined in Haskell . . . . . . . . 874
15.5 Examples of using Monoid . . . . . . . . . . . . . 875
15.6 Why Integer doesn’t have a Monoid . . . . . . . 877
15.7 Why bother? . . . . . . . . . . . . . . . . . . . . . . 883
15.8 Laws . . . . . . . . . . . . . . . . . . . . . . . . . . . . 885
15.9 Different instance, same representation . . . . . 890
15.10 Reusing algebras by asking for algebras . . . . . 893
15.11 Madness . . . . . . . . . . . . . . . . . . . . . . . . . 905
15.12 Better living through QuickCheck . . . . . . . . 906
15.13 Semigroup . . . . . . . . . . . . . . . . . . . . . . . . 917
15.14 Chapter exercises . . . . . . . . . . . . . . . . . . . 925
15.15 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 936
15.16 Follow-up resources . . . . . . . . . . . . . . . . . 937
16 Functor 938
16.1 Functor . . . . . . . . . . . . . . . . . . . . . . . . . . 939
16.2 What’s a functor? . . . . . . . . . . . . . . . . . . . 940
CONTENTS xii
16.3 There’s a whole lot of fmap going round . . . . 943
16.4 Let’s talk about 𝑔, baby . . . . . . . . . . . . . . . . 945
16.5 Functor Laws . . . . . . . . . . . . . . . . . . . . . . 958
16.6 The Good, the Bad, and the Ugly . . . . . . . . . 960
16.7 Commonly used functors . . . . . . . . . . . . . . 966
16.8 Transforming the unapplied type argument . . 983
16.9 QuickChecking Functor instances . . . . . . . . 988
16.10 Exercises: Instances of Func . . . . . . . . . . . . 991
16.11 Ignoring possibilities . . . . . . . . . . . . . . . . . 992
16.12 A somewhat surprising functor . . . . . . . . . . 1000
16.13 More structure, more functors . . . . . . . . . . . 1004
16.14 IO Functor . . . . . . . . . . . . . . . . . . . . . . . . 1005
16.15 What if we want to do something different? . . 1009
16.16 Functors are unique to a datatype . . . . . . . . . 1013
16.17 Chapter exercises . . . . . . . . . . . . . . . . . . . 1015
16.18 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 1020
16.19 Follow-up resources . . . . . . . . . . . . . . . . . 1024
17 Applicative 1025
17.1 Applicative . . . . . . . . . . . . . . . . . . . . . . . 1026
17.2 Defining Applicative . . . . . . . . . . . . . . . . . 1027
17.3 Functor vs. Applicative . . . . . . . . . . . . . . . . 1030
17.4 Applicative functors are monoidal functors . . 1032
17.5 Applicative in use . . . . . . . . . . . . . . . . . . . 1040
17.6 Applicative laws . . . . . . . . . . . . . . . . . . . . 1076
17.7 You knew this was coming . . . . . . . . . . . . . 1085
CONTENTS xiii
17.8 ZipList Monoid . . . . . . . . . . . . . . . . . . . . 1090
17.9 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1104
17.10 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 1107
17.11 Follow-up resources . . . . . . . . . . . . . . . . . 1107
18 Monad 1109
18.1 Monad . . . . . . . . . . . . . . . . . . . . . . . . . . 1110
18.2 Sorry — Monad is not a burrito . . . . . . . . . . 1110
18.3 Do syntax and monads . . . . . . . . . . . . . . . . 1122
18.4 Examples of Monad use . . . . . . . . . . . . . . . 1132
18.5 Monad laws . . . . . . . . . . . . . . . . . . . . . . . 1156
18.6 Application and composition . . . . . . . . . . . 1167
18.7 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1174
18.8 Definition . . . . . . . . . . . . . . . . . . . . . . . . 1177
18.9 Follow-up resources . . . . . . . . . . . . . . . . . 1179
19 Applying structure 1180
19.1 Applied structure . . . . . . . . . . . . . . . . . . . 1181
19.2 Monoid . . . . . . . . . . . . . . . . . . . . . . . . . . 1181
19.3 Functor . . . . . . . . . . . . . . . . . . . . . . . . . . 1188
19.4 Applicative . . . . . . . . . . . . . . . . . . . . . . . 1192
19.5 Monad . . . . . . . . . . . . . . . . . . . . . . . . . . 1199
19.6 An end-to-end example: URL shortener . . . . 1202
19.7 That’s a wrap! . . . . . . . . . . . . . . . . . . . . . . 1220
19.8 Follow-up resources . . . . . . . . . . . . . . . . . 1221
20 Foldable 1222
CONTENTS xiv
20.1 Foldable . . . . . . . . . . . . . . . . . . . . . . . . . 1223
20.2 The Foldable class . . . . . . . . . . . . . . . . . . . 1224
20.3 Revenge of the monoids . . . . . . . . . . . . . . . 1225
20.4 Demonstrating Foldable instances . . . . . . . . 1231
20.5 Some basic derived operations . . . . . . . . . . 1235
20.6 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1242
20.7 Follow-up resources . . . . . . . . . . . . . . . . . 1243
21 Traversable 1244
21.1 Traversable . . . . . . . . . . . . . . . . . . . . . . . 1245
21.2 The Traversable typeclass definition . . . . . . . 1246
21.3 sequenceA . . . . . . . . . . . . . . . . . . . . . . . . 1247
21.4 traverse . . . . . . . . . . . . . . . . . . . . . . . . . . 1250
21.5 So, what’s traversable for? . . . . . . . . . . . . . . 1253
21.6 Morse code revisited . . . . . . . . . . . . . . . . . 1254
21.7 Axing tedious code . . . . . . . . . . . . . . . . . . 1258
21.8 Do all the things . . . . . . . . . . . . . . . . . . . . 1261
21.9 Traversable instances . . . . . . . . . . . . . . . . . 1264
21.10 Traversable Laws . . . . . . . . . . . . . . . . . . . 1268
21.11 Quality Control . . . . . . . . . . . . . . . . . . . . 1269
21.12 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1270
21.13 Follow-up resources . . . . . . . . . . . . . . . . . 1274
22 Reader 1275
22.1 Reader . . . . . . . . . . . . . . . . . . . . . . . . . . 1276
22.2 A new beginning . . . . . . . . . . . . . . . . . . . . 1277
CONTENTS xv
22.3 This is Reader . . . . . . . . . . . . . . . . . . . . . 1287
22.4 Breaking down the Functor of functions . . . . 1288
22.5 But uh, Reader? . . . . . . . . . . . . . . . . . . . . 1293
22.6 Functions have an Applicative too . . . . . . . . 1295
22.7 The Monad of functions . . . . . . . . . . . . . . . 1302
22.8 Reader Monad by itself is kinda boring . . . . . 1308
22.9 You can change what comes below, but not above 1310
22.10 You tend to see ReaderT, not Reader . . . . . . . 1311
22.11 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1312
22.12 Follow-up resources . . . . . . . . . . . . . . . . . 1319
23 State 1320
23.1 State . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1321
23.2 What is state? . . . . . . . . . . . . . . . . . . . . . . 1321
23.3 Random numbers . . . . . . . . . . . . . . . . . . . 1323
23.4 The State newtype . . . . . . . . . . . . . . . . . . . 1327
23.5 Throw down . . . . . . . . . . . . . . . . . . . . . . 1330
23.6 Write State for yourself . . . . . . . . . . . . . . . 1339
23.7 Get a coding job with one weird trick . . . . . . 1341
23.8 Chapter exercises . . . . . . . . . . . . . . . . . . . 1347
23.9 Follow-up resources . . . . . . . . . . . . . . . . . 1350
24 Parser combinators 1351
24.1 Parser combinators . . . . . . . . . . . . . . . . . . 1352
24.2 A few more words of introduction . . . . . . . . 1354
24.3 Understanding the parsing process . . . . . . . . 1355
CONTENTS xvi
24.4 Parsing fractions . . . . . . . . . . . . . . . . . . . . 1371
24.5 Haskell’s parsing ecosystem . . . . . . . . . . . . . 1380
24.6 Alternative . . . . . . . . . . . . . . . . . . . . . . . . 1385
24.7 Parsing configuration files . . . . . . . . . . . . . . 1400
24.8 Character and token parsers . . . . . . . . . . . . 1415
24.9 Polymorphic parsers . . . . . . . . . . . . . . . . . 1421
24.10 Marshalling from an AST to a datatype . . . . . 1429
24.11 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1445
24.12 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 1453
24.13 Follow-up resources . . . . . . . . . . . . . . . . . 1454
25 Composing types 1456
25.1 Composing types . . . . . . . . . . . . . . . . . . . 1457
25.2 Common functions as types . . . . . . . . . . . . 1458
25.3 Two little functors sittin’ in a tree,
L-I-F-T-I-N-G . . . . . . . . . . . . . . . . . . . . . 1463
25.4 Twinplicative . . . . . . . . . . . . . . . . . . . . . . 1466
25.5 Twonad? . . . . . . . . . . . . . . . . . . . . . . . . . 1468
25.6 Exercises: Compose Instances . . . . . . . . . . . 1470
25.7 Monad transformers . . . . . . . . . . . . . . . . . 1472
25.8 IdentityT . . . . . . . . . . . . . . . . . . . . . . . . . 1475
25.9 Finding a pattern . . . . . . . . . . . . . . . . . . . 1493
26 Monad transformers 1496
26.1 Monad transformers . . . . . . . . . . . . . . . . . 1497
26.2 MaybeT . . . . . . . . . . . . . . . . . . . . . . . . . . 1497
CONTENTS xvii
26.3 EitherT . . . . . . . . . . . . . . . . . . . . . . . . . . 1505
26.4 ReaderT . . . . . . . . . . . . . . . . . . . . . . . . . 1507
26.5 StateT . . . . . . . . . . . . . . . . . . . . . . . . . . . 1511
26.6 Types you probably don’t want to use . . . . . . 1516
26.7 Recovering an ordinary type from a transformer 1518
26.8 Lexically inner is structurally outer . . . . . . . 1520
26.9 MonadTrans . . . . . . . . . . . . . . . . . . . . . . 1524
26.10 MonadIO aka zoom-zoom . . . . . . . . . . . . . 1543
26.11 Monad transformers in use . . . . . . . . . . . . . 1547
26.12 Monads do not commute . . . . . . . . . . . . . . 1560
26.13 Transform if you want to . . . . . . . . . . . . . . 1561
26.14 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1562
26.15 Follow-up resources . . . . . . . . . . . . . . . . . 1571
27 Non-strictness 1572
27.1 Laziness . . . . . . . . . . . . . . . . . . . . . . . . . 1573
27.2 Observational Bottom Theory . . . . . . . . . . . 1574
27.3 Outside in, inside out . . . . . . . . . . . . . . . . . 1576
27.4 What does the other way look like? . . . . . . . . 1580
27.5 Call by name, call by need . . . . . . . . . . . . . 1599
27.6 Non-strict evaluation changes what we can do 1600
27.7 Thunk Life . . . . . . . . . . . . . . . . . . . . . . . 1602
27.8 Sharing is caring . . . . . . . . . . . . . . . . . . . . 1606
27.9 Refutable and irrefutable patterns . . . . . . . . 1627
27.10 Bang-patterns . . . . . . . . . . . . . . . . . . . . . 1630
27.11 Strict and StrictData . . . . . . . . . . . . . . . . . 1634
CONTENTS xviii
27.12 Adding strictness . . . . . . . . . . . . . . . . . . . . 1636
27.13 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1642
27.14 Follow-up resources . . . . . . . . . . . . . . . . . 1645
28 Basic libraries 1647
28.1 Basic libraries and data structures . . . . . . . . . 1648
28.2 Benchmarking with Criterion . . . . . . . . . . . 1649
28.3 Profiling your programs . . . . . . . . . . . . . . . 1666
28.4 Constant applicative forms . . . . . . . . . . . . . 1671
28.5 Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1676
28.6 Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1680
28.7 Sequence . . . . . . . . . . . . . . . . . . . . . . . . . 1683
28.8 Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . 1687
28.9 String types . . . . . . . . . . . . . . . . . . . . . . . 1701
28.10 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1712
28.11 Follow-up resources . . . . . . . . . . . . . . . . . 1717
29 IO 1719
29.1 IO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1720
29.2 Where IO explanations go astray . . . . . . . . . 1721
29.3 The reason we need this type . . . . . . . . . . . 1724
29.4 Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . 1725
29.5 IO doesn’t disable sharing for everything . . . . 1733
29.6 Purity is losing meaning . . . . . . . . . . . . . . . 1734
29.7 IO’s Functor, Applicative, and Monad . . . . . . 1737
29.8 Well, then, how do we MVar? . . . . . . . . . . . . 1743
CONTENTS xix
29.9 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1745
29.10 Follow-up resources . . . . . . . . . . . . . . . . . 1746
30 When things go wrong 1748
30.1 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . 1749
30.2 The Exception class and methods . . . . . . . . . 1750
30.3 This machine kills programs . . . . . . . . . . . . 1760
30.4 Want either? Try! . . . . . . . . . . . . . . . . . . . 1768
30.5 The unbearable imprecision of trying . . . . . . 1773
30.6 Why throwIO? . . . . . . . . . . . . . . . . . . . . . 1776
30.7 Making our own exception types . . . . . . . . . 1779
30.8 Surprising interaction with bottom . . . . . . . . 1786
30.9 Asynchronous Exceptions . . . . . . . . . . . . . . 1788
30.10 Follow-up Reading . . . . . . . . . . . . . . . . . . 1792
31 Final project 1794
31.1 Final project . . . . . . . . . . . . . . . . . . . . . . . 1795
31.2 fingerd . . . . . . . . . . . . . . . . . . . . . . . . . . 1795
31.3 Exploring finger . . . . . . . . . . . . . . . . . . . . 1796
31.4 Slightly modernized fingerd . . . . . . . . . . . . 1806
31.5 Chapter Exercises . . . . . . . . . . . . . . . . . . . 1819