Foreword to the first edition |
|
xiv | |
Foreword to the second edition |
|
xvi | |
Preface to the second edition |
|
xviii | |
Acknowledgments |
|
xx | |
About this book |
|
xxii | |
About the authors |
|
xxvii | |
|
Part 1 Introduction to functional programming |
|
|
1 | (140) |
|
1 What is functional programming? |
|
|
3 | (12) |
|
1.1 Understanding the benefits of functional programming |
|
|
4 | (6) |
|
A program with side effects |
|
|
4 | (3) |
|
Afunctional solution: Removing the side effects |
|
|
7 | (3) |
|
1.2 Exactly what is a (pure) function? |
|
|
10 | (1) |
|
1.3 Referential transparency, purity, and the substitution model |
|
|
11 | (2) |
|
|
13 | (2) |
|
2 Getting started with functional programming in Scala |
|
|
15 | (19) |
|
2.1 Introducing Scala the language |
|
|
16 | (4) |
|
|
19 | (1) |
|
2.2 Objects and namespaces |
|
|
20 | (1) |
|
2.3 Higher-order functions: Passing functions to functions |
|
|
21 | (4) |
|
A short detour: Writing loops functionally |
|
|
21 | (3) |
|
Writing our first higher-order function |
|
|
24 | (1) |
|
2.4 Polymorphic functions: Abstracting over types |
|
|
25 | (2) |
|
An example of a polymorphic function |
|
|
25 | (1) |
|
Calling higher-order functions with anonymous functions |
|
|
26 | (1) |
|
2.5 Following types to implementations |
|
|
27 | (3) |
|
|
30 | (4) |
|
3 Functional data structures |
|
|
34 | (33) |
|
3.1 Defining functional data structures |
|
|
35 | (3) |
|
|
38 | (2) |
|
3.3 Data sharing in functional data structures |
|
|
40 | (10) |
|
The efficiency of data sharing |
|
|
42 | (1) |
|
Recursion over lists and generalizing to higher-order functions |
|
|
43 | (4) |
|
More functions for working with lists |
|
|
47 | (2) |
|
Loss of efficiency when assembling list functions from simpler components |
|
|
49 | (1) |
|
|
50 | (5) |
|
|
55 | (1) |
|
|
56 | (11) |
|
4 Handling errors ivithout exceptions |
|
|
67 | (27) |
|
4.1 The good and bad aspects of exceptions |
|
|
68 | (2) |
|
4.2 Possible alternatives to exceptions |
|
|
70 | (1) |
|
|
71 | (10) |
|
Usage patterns for Option |
|
|
72 | (4) |
|
Option composition, lifting, and wrapping exception-oriented APIs |
|
|
76 | (5) |
|
|
81 | (8) |
|
|
83 | (2) |
|
Extracting a Validated type |
|
|
85 | (4) |
|
|
89 | (1) |
|
|
90 | (4) |
|
5 Strictness and laziness |
|
|
94 | (24) |
|
5.1 Strict and nonstrict functions |
|
|
95 | (3) |
|
5.2 Lazy lists: An extended example |
|
|
98 | (3) |
|
Memoizing lazy lists and avoiding recomputation |
|
|
99 | (1) |
|
Helper functions for inspecting lazy lists |
|
|
100 | (1) |
|
5.3 Separating program description from evaluation |
|
|
101 | (3) |
|
5.4 Infinite lazy lists and corecursion |
|
|
104 | (5) |
|
|
109 | (1) |
|
|
110 | (8) |
|
6 Purely junctional state |
|
|
118 | (23) |
|
6.1 Generating random numbers using side effects |
|
|
118 | (2) |
|
6.2 Purely functional random number generation |
|
|
120 | (2) |
|
6.3 Making stateful APIs pure |
|
|
122 | (2) |
|
6.4 A better API for state actions |
|
|
124 | (4) |
|
|
125 | (1) |
|
|
126 | (2) |
|
6.5 A general state action data type |
|
|
128 | (1) |
|
6.6 Purely functional imperative programming |
|
|
129 | (3) |
|
|
132 | (1) |
|
|
133 | (8) |
|
Part 2 Functional design and combinator libraries |
|
|
141 | (112) |
|
7 Purely functional parallelism |
|
|
143 | (36) |
|
7.1 Choosing data types and functions |
|
|
144 | (8) |
|
A data type for parallel computations |
|
|
146 | (2) |
|
Combining parallel computations |
|
|
148 | (2) |
|
|
150 | (2) |
|
7.2 Picking a representation |
|
|
152 | (6) |
|
|
154 | (4) |
|
7.3 The algebra of an API |
|
|
158 | (10) |
|
|
159 | (1) |
|
|
160 | (1) |
|
Breaking the law: A subtle bug |
|
|
161 | (2) |
|
A fully non-blocking Par implementation using actors |
|
|
163 | (5) |
|
7.4 Refining combinators to their most general form |
|
|
168 | (3) |
|
|
171 | (1) |
|
|
172 | (7) |
|
|
179 | (35) |
|
8.1 A brief tour of property-based testing |
|
|
180 | (10) |
|
Choosing data types and functions |
|
|
182 | (1) |
|
Initial snippets of an API |
|
|
183 | (1) |
|
The meaning and API of properties |
|
|
184 | (2) |
|
The meaning and API of generators |
|
|
186 | (1) |
|
Generators that depend on generated values |
|
|
187 | (1) |
|
Refining the Prop data type |
|
|
188 | (2) |
|
8.2 Test case minimization |
|
|
190 | (9) |
|
Using the library and improving its usability |
|
|
192 | (1) |
|
|
192 | (2) |
|
Writing a test suite for parallel computations |
|
|
194 | (5) |
|
8.3 Testing higher-order functions and future directions |
|
|
199 | (1) |
|
8.4 The laws of generators |
|
|
200 | (1) |
|
|
201 | (1) |
|
|
202 | (12) |
|
|
214 | (39) |
|
9.1 Designing an algebra first |
|
|
215 | (5) |
|
|
220 | (5) |
|
Slicing and nonempty repetition |
|
|
222 | (3) |
|
9.3 Handling context sensitivity |
|
|
225 | (1) |
|
9.4 Writing a json parser |
|
|
226 | (2) |
|
|
227 | (1) |
|
|
227 | (1) |
|
|
228 | (5) |
|
|
229 | (1) |
|
|
230 | (2) |
|
Controlling branching and backtracking |
|
|
232 | (1) |
|
9.6 Implementing the algebra |
|
|
233 | (7) |
|
One possible implementation |
|
|
234 | (1) |
|
|
235 | (1) |
|
|
236 | (1) |
|
Failover and backtracking |
|
|
237 | (1) |
|
Context-sensitive parsing |
|
|
238 | (2) |
|
|
240 | (1) |
|
|
241 | (12) |
|
Part 3 Common structures in functional design |
|
|
253 | (100) |
|
|
255 | (28) |
|
|
256 | (2) |
|
10.2 Folding lists with monoids |
|
|
258 | (1) |
|
10.3 Associativity and parallelism |
|
|
259 | (2) |
|
10.4 Example: Parallel parsing |
|
|
261 | (2) |
|
|
263 | (2) |
|
10.6 Foldable data structures |
|
|
265 | (2) |
|
|
267 | (2) |
|
Assembling more complex monoids |
|
|
267 | (2) |
|
Using composed monoids to fuse traversals |
|
|
269 | (1) |
|
|
269 | (2) |
|
|
271 | (12) |
|
|
283 | (30) |
|
11.1 Functors: Generalizing the map function |
|
|
284 | (3) |
|
|
285 | (2) |
|
11.2 Monads: Generalizing the flatMap and unit functions |
|
|
287 | (3) |
|
|
287 | (3) |
|
|
290 | (1) |
|
|
291 | (5) |
|
|
292 | (1) |
|
Proving the associative law for a specific monad |
|
|
293 | (1) |
|
|
294 | (2) |
|
11.5 Just what is a monad? |
|
|
296 | (5) |
|
|
297 | (1) |
|
The State monad and partial type application |
|
|
298 | (3) |
|
|
301 | (1) |
|
|
302 | (11) |
|
12 Applicative and traversable junctors |
|
|
313 | (40) |
|
|
314 | (1) |
|
12.2 The Applicative trait |
|
|
314 | (3) |
|
12.3 The difference between monads and applicative functors |
|
|
317 | (3) |
|
The Option applicative versus the Option monad |
|
|
317 | (1) |
|
The Parser applicative versus the Parser monad |
|
|
318 | (2) |
|
12.4 The advantages of applicative functors |
|
|
320 | (5) |
|
Not all applicative functors are monads |
|
|
320 | (5) |
|
12.5 The applicative laws |
|
|
325 | (4) |
|
|
326 | (1) |
|
|
326 | (1) |
|
|
327 | (2) |
|
12.6 Traversable functors |
|
|
329 | (2) |
|
|
331 | (6) |
|
From monoids to applicative functors |
|
|
332 | (1) |
|
|
333 | (2) |
|
Combining traversable structures |
|
|
335 | (1) |
|
|
336 | (1) |
|
|
336 | (1) |
|
|
336 | (1) |
|
|
337 | (2) |
|
|
339 | (14) |
|
|
353 | (98) |
|
13 External effects and I/O |
|
|
355 | (49) |
|
|
356 | (1) |
|
|
357 | (6) |
|
|
358 | (4) |
|
Benefits and drawbacks of the simple 10 type |
|
|
362 | (1) |
|
13.3 Avoiding the Stack Over flow Error |
|
|
363 | (5) |
|
Fteifying control flow as data constructors |
|
|
363 | (3) |
|
Trampolining: A general solution to stack overflow |
|
|
366 | (2) |
|
13.4 A more nuanced I/O type |
|
|
368 | (9) |
|
|
370 | (1) |
|
A monad that supports only console I/O |
|
|
371 | (4) |
|
|
375 | (2) |
|
13.5 Non-blocking and asynchronous I/O |
|
|
377 | (6) |
|
|
379 | (4) |
|
|
383 | (2) |
|
13.7 A general-purpose I/O type |
|
|
385 | (1) |
|
The main program at the end of the universe |
|
|
386 | (1) |
|
13.8 Why the IO type is insufficient for streaming I/O |
|
|
386 | (2) |
|
|
388 | (2) |
|
|
390 | (5) |
|
Local effects and mutable state |
|
|
394 | (1) |
|
14.1 Purely functional mutable state |
|
|
395 | (1) |
|
14.2 A data type to enforce the scoping of side effects |
|
|
396 | (8) |
|
A little language for scoped mutation |
|
|
397 | (1) |
|
An algebra of mutable references |
|
|
398 | (2) |
|
Running mutable slate actions |
|
|
400 | (2) |
|
|
402 | (2) |
|
14 purely functional in-place quicksort |
|
|
404 | (6) |
|
14.3 Purity is contextual |
|
|
405 | (2) |
|
What counts as a side effect |
|
|
406 | (1) |
|
|
407 | (1) |
|
|
408 | (2) |
|
15 Stream processing and incremental I/O |
|
|
410 | (41) |
|
15.1 Problems with imperative I/O: An example |
|
|
411 | (3) |
|
15.2 Simple stream transformations |
|
|
414 | (10) |
|
|
415 | (6) |
|
Composing stream transformations |
|
|
421 | (2) |
|
|
423 | (1) |
|
15.3 Extensible pulls and streams |
|
|
424 | (18) |
|
Effectful streaming computations |
|
|
430 | (1) |
|
|
431 | (4) |
|
|
435 | (6) |
|
Dynamic resource allocation |
|
|
441 | (1) |
|
|
442 | (1) |
|
|
443 | (1) |
|
|
444 | (7) |
Index |
|
451 | |