Foreword |
|
xiii | |
Preface |
|
xv | |
Acknowledgments |
|
xvii | |
About This Book |
|
xix | |
Part 1 Introduction To Functional Programming |
|
1 | (114) |
|
1 What is functional programming? |
|
|
3 | (14) |
|
1.1 The benefits of FP: A simple example |
|
|
5 | (6) |
|
A program with side effects |
|
|
5 | (2) |
|
A functional solution: Removing the side effects |
|
|
7 | (4) |
|
1.2 Exactly what is a (pure) function? |
|
|
11 | (1) |
|
1.3 RT, purity, and the substitution model |
|
|
12 | (3) |
|
|
15 | (2) |
|
2 Getting started with functional programming in Kotlin |
|
|
17 | (14) |
|
2.1 Higher-order functions: Passing functions to functions |
|
|
18 | (5) |
|
A short detour: Writing loops functionally |
|
|
18 | (2) |
|
Writing our first higher-order function |
|
|
20 | (3) |
|
2.2 Polymorphic functions: Abstracting over types |
|
|
23 | (4) |
|
An example of a polymorphic function |
|
|
24 | (2) |
|
Calling HOFs with anonymous functions |
|
|
26 | (1) |
|
2.3 Following types to implementations |
|
|
27 | (4) |
|
3 Functional data structures |
|
|
31 | (25) |
|
3.1 Defining functional data structures |
|
|
32 | (2) |
|
3.2 Working with functional data structures |
|
|
34 | (6) |
|
The "when" construct for matching by type |
|
|
37 | (1) |
|
The when construct as an alternative to if-else logic |
|
|
37 | (1) |
|
Pattern matching and how it differs from Kotlin matching |
|
|
38 | (2) |
|
3.3 Data sharing in functional data structures |
|
|
40 | (3) |
|
The efficiency of data sharing |
|
|
42 | (1) |
|
3.4 Recursion over lists and generalizing to HOFs |
|
|
43 | (8) |
|
More functions for working with lists |
|
|
47 | (2) |
|
Lists in the Kotlin standard library |
|
|
49 | (2) |
|
Inefficiency of assembling list functions from simpler components |
|
|
51 | (1) |
|
|
51 | (5) |
|
4 Handling errors without exceptions |
|
|
56 | (21) |
|
4.1 The problems with throwing exceptions |
|
|
57 | (2) |
|
4.2 Problematic alternatives to exceptions |
|
|
59 | (2) |
|
|
60 | (1) |
|
|
60 | (1) |
|
4.3 Encoding success conditions with Option |
|
|
61 | (11) |
|
Usage patterns for Option |
|
|
61 | (6) |
|
Option composition, lifting, and wrapping exception-oriented APIs |
|
|
67 | (4) |
|
For-comprehensions with Option |
|
|
71 | (1) |
|
4.4 Encoding success and failure conditions with Either |
|
|
72 | (5) |
|
For-comprehensions with Either |
|
|
74 | (3) |
|
5 Strictness and laziness |
|
|
77 | (19) |
|
5.1 Strict and non-strict functions |
|
|
79 | (3) |
|
5.2 An extended example: Lazy lists |
|
|
82 | (3) |
|
Memoizing streams and avoiding recomputation |
|
|
83 | (1) |
|
Helper functions for inspecting streams |
|
|
84 | (1) |
|
5.3 Separating program description from evaluation |
|
|
85 | (4) |
|
5.4 Producing infinite data streams through corecursive functions |
|
|
89 | (5) |
|
|
94 | (2) |
|
6 Purely functional state |
|
|
96 | (19) |
|
6.1 Generating random numbers using side effects |
|
|
97 | (2) |
|
6.2 Purely functional random number generation |
|
|
99 | (1) |
|
6.3 Making stateful APIs pure |
|
|
100 | (3) |
|
6.4 An implicit approach to passing state actions |
|
|
103 | (5) |
|
More power by combining state actions |
|
|
104 | (2) |
|
Recursive retries through nested state actions |
|
|
106 | (1) |
|
Applying the combinator API to the initial example |
|
|
107 | (1) |
|
6.5 A general state action data type |
|
|
108 | (1) |
|
6.6 Purely functional imperative programming |
|
|
109 | (5) |
|
|
114 | (1) |
Part 2 Functional Design And Combinator Libraries |
|
115 | (94) |
|
7 Purely functional parallelism |
|
|
117 | (33) |
|
7.1 Choosing data types and functions |
|
|
118 | (8) |
|
A data type for parallel computations |
|
|
120 | (1) |
|
Combining parallel computations to ensure concurrency |
|
|
121 | (3) |
|
Marking computations to be forked explicitly |
|
|
124 | (2) |
|
7.2 Picking a representation |
|
|
126 | (3) |
|
7.3 Refining the API with the end user in mind |
|
|
129 | (5) |
|
7.4 Reasoning about the API in terms of algebraic equations |
|
|
134 | (11) |
|
|
134 | (2) |
|
|
136 | (2) |
|
Using actors for a non-blocking implementation |
|
|
138 | (7) |
|
7.5 Refining combinators to their most general form |
|
|
145 | (5) |
|
|
150 | (27) |
|
8.1 A brief tour of property-based testing |
|
|
151 | (2) |
|
8.2 Choosing data types and functions |
|
|
153 | (10) |
|
Gathering initial snippets for a possible API |
|
|
153 | (1) |
|
Exploring the meaning and API of properties |
|
|
154 | (3) |
|
Discovering the meaning and API of generators |
|
|
157 | (2) |
|
Generators that depend on generated values |
|
|
159 | (1) |
|
Refining the property data type |
|
|
160 | (3) |
|
8.3 Test case minimization |
|
|
163 | (3) |
|
8.4 Using the library and improving the user experience |
|
|
166 | (7) |
|
|
166 | (2) |
|
Writing a test suite for parallel computations |
|
|
168 | (5) |
|
8.5 Generating higher-order functions and other possibilities |
|
|
173 | (2) |
|
8.6 The laws of generators |
|
|
175 | (1) |
|
|
175 | (2) |
|
|
177 | (32) |
|
|
179 | (4) |
|
A parser to recognize single characters |
|
|
179 | (1) |
|
A parser to recognize entire strings |
|
|
180 | (1) |
|
A parser to recognize repetition |
|
|
181 | (2) |
|
9.2 One possible approach to designing an algebra |
|
|
183 | (6) |
|
Counting character repetition |
|
|
183 | (2) |
|
Slicing and nonempty repetition |
|
|
185 | (4) |
|
9.3 Handling context sensitivity |
|
|
189 | (2) |
|
9.4 Writing a JSON parser |
|
|
191 | (3) |
|
Defining expectations of aJSON parser |
|
|
191 | (1) |
|
|
192 | (1) |
|
|
193 | (1) |
|
9.5 Surfacing errors through reporting |
|
|
194 | (6) |
|
First attempt at representing errors |
|
|
196 | (1) |
|
Accumulating errors through error nesting |
|
|
197 | (1) |
|
Controlling branching and backtracking |
|
|
198 | (2) |
|
9.6 Implementing the algebra |
|
|
200 | (7) |
|
Building up the algebra implementation gradually |
|
|
201 | (1) |
|
Sequencing parsers after each other |
|
|
202 | (1) |
|
Capturing error messages through labeling parsers |
|
|
203 | (2) |
|
Recovering from error conditions and backtracking over them |
|
|
205 | (1) |
|
Propagating state through context-sensitive parsers |
|
|
206 | (1) |
|
|
207 | (2) |
Part 3 Common Structures In Functional Design |
|
209 | (82) |
|
|
211 | (20) |
|
|
212 | (5) |
|
10.2 Folding lists with monoids |
|
|
217 | (1) |
|
10.3 Associativity and parallelism |
|
|
218 | (3) |
|
10.4 Example: Parallel parsing |
|
|
221 | (2) |
|
10.5 Foldable data structures |
|
|
223 | (4) |
|
|
227 | (4) |
|
Assembling more complex monoids |
|
|
227 | (2) |
|
Using composed monoids to fuse traversals |
|
|
229 | (2) |
|
|
231 | (27) |
|
|
232 | (3) |
|
Defining the functor by generalizing the map function |
|
|
232 | (2) |
|
The importance of laws and their relation to the functor |
|
|
234 | (1) |
|
11.2 Monads: Generalizing the flatMap and unit functions |
|
|
235 | (4) |
|
Introducing the Monad interface |
|
|
236 | (3) |
|
|
239 | (2) |
|
|
241 | (7) |
|
|
242 | (1) |
|
Proving the associative law for a specific monad |
|
|
243 | (3) |
|
The left and right identity laws |
|
|
246 | (2) |
|
11.5 Just what is a monad? |
|
|
248 | (10) |
|
|
249 | (1) |
|
The State monad and partial type application |
|
|
250 | (8) |
|
12 Applicative and traversable functors |
|
|
258 | (33) |
|
12.1 Generalizing monads for reusability |
|
|
259 | (1) |
|
12.2 Applicatives as an alternative abstraction to the monad |
|
|
260 | (5) |
|
12.3 The difference between monads and applicative functors |
|
|
265 | (3) |
|
The Option applicative vs. the Option monad |
|
|
265 | (1) |
|
The Parser applicative vs. the Parser monad |
|
|
266 | (2) |
|
12.4 The advantages of applicative functors |
|
|
268 | (4) |
|
Not all applicative functors are monads |
|
|
268 | (4) |
|
12.5 Reasoning about programs through the applicative laws |
|
|
272 | (5) |
|
Laws of left and right identity |
|
|
272 | (1) |
|
|
273 | (1) |
|
|
274 | (3) |
|
12.6 Abstracting traverse and sequence using traversable functors |
|
|
277 | (2) |
|
12.7 Using Traversable to iteratively transform higher kinds |
|
|
279 | (14) |
|
From monoids to applicative functors |
|
|
280 | (2) |
|
Traversing collections while propagating state actions |
|
|
282 | (4) |
|
Combining traversable structures |
|
|
286 | (1) |
|
Traversal fusion for single pass efficiency |
|
|
287 | (1) |
|
Simultaneous traversal of nested traversable structures |
|
|
288 | (1) |
|
Pitfalls and workarounds for monad composition |
|
|
288 | (3) |
Part 4 Effects And I/O |
|
291 | (89) |
|
13 External effects and I/O |
|
|
293 | (33) |
|
13.1 Factoring effects out of an effectful program |
|
|
294 | (2) |
|
13.2 Introducing the IO type to separate effectful code |
|
|
296 | (7) |
|
|
297 | (5) |
|
Benefits and drawbacks of the simple 10 type |
|
|
302 | (1) |
|
13.3 Avoiding stack overflow errors by reification and trampolining |
|
|
303 | (6) |
|
Reifying control flow as data constructors |
|
|
304 | (3) |
|
Trampolining: A general solution to stack overflow |
|
|
307 | (2) |
|
13.4 A more nuanced IO type |
|
|
309 | (10) |
|
|
311 | (1) |
|
A monad that supports only console I/O |
|
|
312 | (4) |
|
Testing console I/O by using pure interpreters |
|
|
316 | (3) |
|
13.5 Non-blocking and asynchronous I/O |
|
|
319 | (2) |
|
13.6 A general-purpose IO type |
|
|
321 | (1) |
|
The main program at the end of the universe |
|
|
321 | (1) |
|
13.7 Why the IO type is insufficient for streaming I/O |
|
|
322 | (4) |
|
14 Local effects and mutable state |
|
|
326 | (18) |
|
14.1 State mutation is legal in pure functional code |
|
|
327 | (2) |
|
14.2 A data type to enforce scoping of side effects |
|
|
329 | (11) |
|
A domain-specific language for scoped mutation |
|
|
330 | (1) |
|
An algebra of mutable references |
|
|
331 | (3) |
|
Running mutable state actions |
|
|
334 | (2) |
|
The mutable array represented as a data type for the ST monad |
|
|
336 | (2) |
|
A purely functional in-place quicksort |
|
|
338 | (2) |
|
14.3 Purity is contextual |
|
|
340 | (4) |
|
|
340 | (1) |
|
What counts as a side effect? |
|
|
341 | (3) |
|
15 Stream processing and incremental I/O |
|
|
344 | (36) |
|
15.1 Problems with imperative I/O: An example |
|
|
345 | (3) |
|
15.2 Transforming streams with simple transducers |
|
|
348 | (10) |
|
Combinators for building stream transducers |
|
|
350 | (4) |
|
Combining multiple transducers by appending and composing |
|
|
354 | (3) |
|
Stream transducers for file processing |
|
|
357 | (1) |
|
15.3 An extensible process type for protocol parameterization |
|
|
358 | (19) |
|
Sources for stream emission |
|
|
361 | (2) |
|
Ensuring resource safety in stream transducers |
|
|
363 | (4) |
|
Applying transducers to a single-input stream |
|
|
367 | (3) |
|
|
370 | (3) |
|
Sinks for output processing |
|
|
373 | (2) |
|
Hiding effects in effectful channels |
|
|
375 | (1) |
|
Dynamic resource allocation |
|
|
376 | (1) |
|
15.4 Application of stream transducers in the real world |
|
|
377 | (3) |
Appendix A Exercise Hints And Tips |
|
380 | (13) |
Appendix B Exercise Solutions |
|
393 | (67) |
Appendix C Higher-Kinded Types |
|
460 | (7) |
Appendix D Type Classes |
|
467 | (4) |
Index |
|
471 | |