《Haskell Wiki Books》

【实例截图】

【核心代码】

Contents
1 Haskell Basics 3
2 Getting set up 5
2.1 Installing Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Very first steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Variables and functions 9
3.1 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Haskell source files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.3 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.4 Variables in imperative languages . . . . . . . . . . . . . . . . . . . . . . . 12
3.5 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.6 Local definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4 Truth values 19
4.1 Equality and other comparisons . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2 Boolean values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.3 Infix operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.4 Boolean operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.5 Guards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5 Type basics 27
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.2 Using the interactive :type command . . . . . . . . . . . . . . . . . . . . 28
5.3 Functional types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.4 Type signatures in code . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
6 Lists and tuples 39
6.1 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6.2 Tuples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6.3 Retrieving values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
6.4 Polymorphic types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
7 Type basics II 49
7.1 The Num class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
7.2 Numeric types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
7.3 Classes beyond numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
III
Contents
8 Building vocabulary 55
8.1 Function composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
8.2 The need for a vocabulary . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
8.3 Prelude and the hierarchical libraries . . . . . . . . . . . . . . . . . . . . . 57
8.4 One exhibit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
8.5 Acquiring vocabulary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
9 Next steps 61
9.1 if / then / else . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
9.2 Introducing pattern matching . . . . . . . . . . . . . . . . . . . . . . . . . 62
9.3 Tuple and list patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
9.4 let bindings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
10 Simple input and output 69
10.1 Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
10.2 Actions under the microscope . . . . . . . . . . . . . . . . . . . . . . . . . 74
10.3 Learn more . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
11 Elementary Haskell 79
12 Recursion 81
12.1 Numeric recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
12.2 List-based recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
12.3 Don't get TOO excited about recursion... . . . . . . . . . . . . . . . . . . 88
12.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
13 More about lists 89
13.1 Rebuilding lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
13.2 Generalizing even further . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
13.3 The map function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
13.4 Tips and Tricks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
14 List processing 97
14.1 Folds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
14.2 Scans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
14.3 filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
14.4 List comprehensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
15 Type declarations 107
15.1 data and constructor functions . . . . . . . . . . . . . . . . . . . . . . . . 107
15.2 Deconstructing types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
15.3 type for making type synonyms . . . . . . . . . . . . . . . . . . . . . . . . 110
16 Pattern matching 113
16.1 Analysing pattern matching . . . . . . . . . . . . . . . . . . . . . . . . . . 113
16.2 The connection with constructors . . . . . . . . . . . . . . . . . . . . . . . 114
16.3 Matching literal values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
16.4 Syntax tricks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
16.5 Where we can use pattern matching . . . . . . . . . . . . . . . . . . . . . 118
IV
Contents
17 Control structures 121
17.1 if and guards revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
17.2 case expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
17.3 Controlling actions, revisited . . . . . . . . . . . . . . . . . . . . . . . . . . 124
18 More on functions 127
18.1 let and where revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
18.2 Anonymous Functions - lambdas . . . . . . . . . . . . . . . . . . . . . . . 128
18.3 Operators and sections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
19 Higher order functions and Currying 131
19.1 The Quickest Sorting Algorithm In Town . . . . . . . . . . . . . . . . . . . 131
19.2 Now, How Do We Use It? . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
19.3 Tweaking What We Already Have . . . . . . . . . . . . . . . . . . . . . . . 133
19.4 quickSort, Take Two . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
19.5 But What Did We Gain? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
19.6 Higher-Order Functions and Types . . . . . . . . . . . . . . . . . . . . . . 134
19.7 Currying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
19.8 Function manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
20 Using GHCi effectively 139
20.1 User interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
21 Intermediate Haskell 141
22 Modules 143
22.1 Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
22.2 Importing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
22.3 Exporting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
23 Indentation 149
23.1 The golden rule of indentation . . . . . . . . . . . . . . . . . . . . . . . . . 149
23.2 A mechanical translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
23.3 Layout in action . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
24 More on datatypes 155
24.1 Enumerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
24.2 Named Fields (Record Syntax) . . . . . . . . . . . . . . . . . . . . . . . . 155
24.3 Parameterized Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
25 Other data structures 161
25.1 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
25.2 Other datatypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
26 Classes and types 169
26.1 Classes and instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
26.2 Deriving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
26.3 Class inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
26.4 Standard classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
V
Contents
26.5 Type constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
26.6 A concerted example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
27 The Functor class 177
27.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
27.2 Introducing Functor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
27.3 What did we gain? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
28 Monads 181
29 Understanding monads 183
29.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
29.2 Notions of Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
29.3 Monad Laws . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
29.4 Monads and Category Theory . . . . . . . . . . . . . . . . . . . . . . . . . 188
30 The Maybe monad 191
30.1 Safe functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
30.2 Lookup tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
30.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
31 The List monad 195
31.1 Instantiation as monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
31.2 Bunny invasion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
31.3 Noughts and crosses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
31.4 List comprehensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
32 do Notation 199
32.1 Translating the then operator . . . . . . . . . . . . . . . . . . . . . . . . . 199
32.2 Translating the bind operator . . . . . . . . . . . . . . . . . . . . . . . . . 200
32.3 Example: user-interactive program . . . . . . . . . . . . . . . . . . . . . . 201
32.4 Returning values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
32.5 It is just sugar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
33 The IO monad 205
33.1 The Problem: Input/Output and Purity . . . . . . . . . . . . . . . . . . . 205
33.2 Combining Pure Functions and Input/Output . . . . . . . . . . . . . . . . 206
33.3 IO facts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
33.4 Monadic control structures . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
34 The State monad 209
34.1 Pseudo-Random Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
34.2 Definition of the State Monad . . . . . . . . . . . . . . . . . . . . . . . . . 211
34.3 Example: Rolling Dice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
34.4 Pseudo-random values of different types . . . . . . . . . . . . . . . . . . . 219
35 Additive monads (MonadPlus) 221
35.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
35.2 Example: parallel parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
VI
Contents
35.3 The MonadPlus laws . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
35.4 Useful functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
35.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
35.6 Relationship with monoids . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
36 Monadic parser combinators 227
37 Monad transformers 229
37.1 Password validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
37.2 A simple monad transformer: MaybeT . . . . . . . . . . . . . . . . . . . . . 230
37.3 A plethora of transformers . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
37.4 Lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
37.5 Implementing transformers . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
37.6 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
38 Practical monads 239
38.1 Parsing monads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
38.2 Generic monads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
38.3 Stateful monads for concurrent applications . . . . . . . . . . . . . . . . . 250
39 Advanced Haskell 255
40 Arrows 257
40.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
40.2 proc and the arrow tail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
40.3 do notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
40.4 Monads and arrows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
41 Understanding arrows 261
41.1 The factory and conveyor belt metaphor . . . . . . . . . . . . . . . . . . . 261
41.2 Plethora of robots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
41.3 Functions are arrows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
41.4 The arrow notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
41.5 Maybe functor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
41.6 Using arrows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
41.7 Monads can be arrows too . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
41.8 Arrows in practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
41.9 See also . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
41.10 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
42 Continuation passing style (CPS) 277
42.1 What are continuations? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
42.2 Passing continuations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
42.3 The Cont monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
42.4 callCC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
42.5 Example: a complicated control structure . . . . . . . . . . . . . . . . . . 284
42.6 Example: exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
42.7 Example: coroutines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
VII
Contents
43 Zippers 287
43.1 Theseus and the Zipper . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
43.2 Differentiation of data types . . . . . . . . . . . . . . . . . . . . . . . . . . 296
43.3 See Also . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
44 Applicative Functors 305
44.1 Functors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
44.2 Applicative Functors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
44.3 Monads and Applicative Functors . . . . . . . . . . . . . . . . . . . . . . . 308
44.4 ZipLists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
44.5 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
45 Monoids 311
45.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
45.2 Haskell definition and laws . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
45.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
45.4 Homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
45.5 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
46 Mutable objects 317
46.1 The ST and IO monads . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
46.2 State references: STRef and IORef . . . . . . . . . . . . . . . . . . . . . . 317
46.3 Mutable arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
46.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
47 Concurrency 319
47.1 Concurrency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
47.2 When do you need it? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
47.3 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
47.4 Software Transactional Memory . . . . . . . . . . . . . . . . . . . . . . . . 320
48 Fun with Types 323
49 Polymorphism basics 325
49.1 Parametric Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
49.2 System F . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
49.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
49.4 Other forms of Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . 328
49.5 Free Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
49.6 See also . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
50 Existentially quantified types 331
50.1 The forall keyword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
50.2 Example: heterogeneous lists . . . . . . . . . . . . . . . . . . . . . . . . . 332
50.3 Explaining the term existential . . . . . . . . . . . . . . . . . . . . . . . . 333
50.4 Example: runST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
50.5 Quantification as a primitive . . . . . . . . . . . . . . . . . . . . . . . . . . 337
50.6 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
VIII
Contents
51 Advanced type classes 339
51.1 Multi-parameter type classes . . . . . . . . . . . . . . . . . . . . . . . . . . 339
51.2 Functional dependencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
52 Phantom types 343
52.1 Phantom types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
53 Generalised algebraic data-types (GADT) 345
53.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
53.2 Understanding GADTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
53.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
53.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
53.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
54 Type constructors & Kinds 357
54.1 Kinds for C users . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
55 Wider Theory 359
56 Denotational semantics 361
56.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
56.2 Bottom and Partial Functions . . . . . . . . . . . . . . . . . . . . . . . . . 364
56.3 Recursive Definitions as Fixed Point Iterations . . . . . . . . . . . . . . . . 368
56.4 Strict and Non-Strict Semantics . . . . . . . . . . . . . . . . . . . . . . . . 373
56.5 Algebraic Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
56.6 Other Selected Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
56.7 External Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
57 Category theory 389
57.1 Introduction to categories . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
57.2 Functors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
57.3 Monads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396
57.4 The monad laws and their importance . . . . . . . . . . . . . . . . . . . . 398
57.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
58 The Curry-Howard isomorphism 405
58.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
58.2 Logical operations and their equivalents . . . . . . . . . . . . . . . . . . . 407
58.3 Axiomatic logic and the combinatory calculus . . . . . . . . . . . . . . . . 409
58.4 Sample proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
58.5 Intuitionistic vs classical logic . . . . . . . . . . . . . . . . . . . . . . . . . 411
59 fix and recursion 413
59.1 Introducing fix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
59.2 fix and fixed points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
59.3 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
59.4 The typed lambda calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
59.5 Fix as a data type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
IX
Contents
60 Haskell Performance 421
61 Introduction 423
61.1 Execution Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
61.2 Algorithms & Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . 427
61.3 Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
62 Step by Step Examples 431
62.1 Tight loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
62.2 CSV Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
62.3 Space Leak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432
63 Graph reduction 433
63.1 Notes and TODOs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
63.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
63.3 Evaluating Expressions by Lazy Evaluation . . . . . . . . . . . . . . . . . 434
63.4 Controlling Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441
63.5 Reasoning about Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
63.6 Implementation of Graph reduction . . . . . . . . . . . . . . . . . . . . . . 444
63.7 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444
64 Laziness 445
64.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
64.2 Thunks and Weak head normal form . . . . . . . . . . . . . . . . . . . . . 445
64.3 Lazy and strict functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
64.4 Lazy pattern matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
64.5 Benefits of nonstrict semantics . . . . . . . . . . . . . . . . . . . . . . . . . 453
64.6 Common nonstrict idioms . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
64.7 Conclusions about laziness . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
64.8 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
65 Strictness 459
65.1 Difference between strict and lazy evaluation . . . . . . . . . . . . . . . . . 459
65.2 Why laziness can be problematic . . . . . . . . . . . . . . . . . . . . . . . 459
65.3 Strictness annotations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
65.4 seq . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
65.5 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
66 Algorithm complexity 461
66.1 Optimising . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
67 Libraries Reference 463
68 The Hierarchical Libraries 465
68.1 Haddock Documentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
69 Lists 467
69.1 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
69.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
X
Contents
69.3 Basic list usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468
69.4 List utilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
70 Arrays 471
70.1 Quick reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
70.2 Immutable arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
70.3 Mutable IO arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
70.4 Mutable arrays in ST monad . . . . . . . . . . . . . . . . . . . . . . . . . 472
70.5 Freezing and thawing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
70.6 DiffArray . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
70.7 Unboxed arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
70.8 StorableArray . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
70.9 The Haskell Array Preprocessor (STPP) . . . . . . . . . . . . . . . . . . . 477
70.10 ArrayRef library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
70.11 Unsafe operations and running over array elements . . . . . . . . . . . . . 478
70.12 GHC-specific topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
71 Maybe 483
71.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
71.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
71.3 Library functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
72 Maps 489
72.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
72.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
72.3 Library functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
72.4 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 490
73 IO 493
73.1 The IO Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493
73.2 A File Reading Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
73.3 Another way of reading files . . . . . . . . . . . . . . . . . . . . . . . . . . 496
74 Random Numbers 499
74.1 Random examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499
74.2 The Standard Random Number Generator . . . . . . . . . . . . . . . . . . 500
74.3 Using QuickCheck to Generate Random Data . . . . . . . . . . . . . . . . 503
75 General Practices 507
76 Building a standalone application 509
77 Debugging 511
77.1 Debug prints with Debug.Trace . . . . . . . . . . . . . . . . . . . . . . . . 511
77.2 Incremental development with GHCi . . . . . . . . . . . . . . . . . . . . . 513
77.3 Debugging with Hat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
77.4 General tips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
XI
Contents
78 Testing 515
78.1 Quickcheck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515
78.2 HUnit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518
79 Packaging your software (Cabal) 519
79.1 Recommended tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
79.2 Structure of a simple project . . . . . . . . . . . . . . . . . . . . . . . . . . 520
79.3 Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526
79.4 Automation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528
79.5 Licenses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 529
79.6 Releases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530
79.7 Hosting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530
79.8 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
80 Using the Foreign Function Interface (FFI) 533
80.1 Calling C from Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533
80.2 Calling Haskell from C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546
81 Generic Programming : Scrap your boilerplate 549
81.1 Serialization Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549
81.2 Comparing Haskell ASTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549
81.3 TODO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550
82 Specialised Tasks 551
83 Graphical user interfaces (GUI) 553
83.1 Getting and running wxHaskell . . . . . . . . . . . . . . . . . . . . . . . . 553
83.2 Hello World . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554
83.3 Controls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555
83.4 Layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557
83.5 Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 561
83.6 Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
84 Databases 565
84.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565
84.2 Installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565
84.3 General Workflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567
84.4 Running SQL Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . 568
84.5 Transaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568
84.6 Calling Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568
85 Web programming 569
86 Working with XML 571
86.1 Getting acquainted with HXT . . . . . . . . . . . . . . . . . . . . . . . . . 571
87 Using Regular Expressions 575
XII
Contents
88 Parsing Mathematical Expressions 577
88.1 First Warmup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577
88.2 Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578
88.3 Structure Emerges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580
88.4 Whitespace and applicative notation . . . . . . . . . . . . . . . . . . . . . 581
89 Contributors 585
List of Figures 589
90 Licenses 593
90.1 GNU GENERAL PUBLIC LICENSE . . . . . . . . . . . . . . . . . . . . . 593
90.2 GNU Free Documentation License . . . . . . . . . . . . . . . . . . . . . . . 594
90.3 GNU Lesser General Public License . . . . . . . . . . . . . . . . . . . . . . 595