Foreword by Cay Horstmann  xxiii
Preface    xxv
Acknowledgments    xxxv
About the Author    xxxvii
Â
Part I. Functional Programming    1
Chapter 1: Concepts of Functional Programming    3
    1.1 What Is Functional Programming?     3
    1.2 Functions    4
    1.3 From Functions to Functional Programming Concepts    6
    1.4 Summary    7
Â
Chapter 2: Functions in Programming Languages     9
    2.1 Defining Functions     9
    2.2 Composing Functions     10
    2.3 Functions Defined as Methods     12
    2.4 Operators Defined as Methods     12
    2.5 Extension Methods   13
    2.6 Local Functions     14
    2.7 Repeated Arguments     15
    2.8 Optional Arguments     16
    2.9 Named Arguments     16
    2.10 Type Parameters     17
    2.11 Summary     19
Â
Chapter 3: Immutability     21
    3.1 Pure and Impure Functions     21
    3.2 Actions     23
    3.3 Expressions Versus Statements     25
    3.4 Functional Variables     26
    3.5 Immutable Objects     28
    3.6 Implementation of Mutable State     29
    3.7 Functional Lists     31
    3.8 Hybrid Designs     32
    3.9 Updating Collections of Mutable/Immutable Objects     35
    3.10 Summary     36
Â
Chapter 4: Case Study: Active–Passive Sets     39
    4.1 Object-Oriented Design     39
    4.2 Functional Values     41
    4.3 Functional Objects     43
    4.4 Summary     44
Â
Chapter 5: Pattern Matching and Algebraic Data Types     47
    5.1 Functional Switch     47
    5.2 Tuples     48
    5.3 Options     50
    5.4 Revisiting Functional Lists     51
    5.5 Trees     53
    5.6 Illustration: List Zipper     56
    5.7 Extractors     59
    5.8 Summary     60
Â
Chapter 6: Recursive Programming     63
    6.1 The Need for Recursion     63
    6.2 Recursive Algorithms     65
    6.3 Key Principles of Recursive Algorithms     67
    6.4 Recursive Structures     69
    6.5 Tail Recursion     71
    6.6 Examples of Tail Recursive Functions     73
    6.7 Summary     77
Â
Chapter 7: Recursion on Lists     79
    7.1 Recursive Algorithms as Equalities     79
    7.2 Traversing Lists     80
    7.3 Returning Lists     82
    7.4 Building Lists from the Execution Stack     84
    7.5 Recursion on Multiple/Nested Lists     85
    7.6 Recursion on Sublists Other Than the Tail     88
    7.7 Building Lists in Reverse Order     90
    7.8 Illustration: Sorting     92
    7.9 Building Lists Efficiently     94
    7.10 Summary     96
Â
Chapter 8: Case Study: Binary Search Trees     99
    8.1 Binary Search Trees     99
    8.2 Sets of Integers as Binary Search Trees     100
    8.3 Implementation Without Rebalancing     102
    8.4 Self-Balancing Trees     107
    8.5 Summary     113
Â
Chapter 9: Higher-Order Functions     115
    9.1 Functions as Values     115
    9.2 Currying     118
    9.3 Function Literals     120
    9.4 Functions Versus Methods     123
    9.5 Single-Abstract-Method Interfaces     124
    9.6 Partial Application     125
    9.7 Closures     130
    9.8 Inversion of Control     133
    9.9 Summary     133
Â
Chapter 10: Standard Higher-Order Functions     137
    10.1 Functions with Predicate Arguments     137
    10.2 map and foreach     140
    10.3 atMap     141
    10.4 fold and reduce     146
    10.5 iterate, tabulate, and unfold     148
    10.6 sortWith, sortBy, maxBy, and minBy     149
    10.7 groupBy and groupMap     150
    10.8 Implementing Standard Higher-Order Functions     152
    10.9 foreach, map, atMap, and for-Comprehensions     152
    10.10 Summary     155
Â
Chapter 11: Case Study: File Systems as Trees     157
    11.1 Design Overview     157
    11.2 A Node-Searching Helper Function     158
    11.3 String Representation     158
    11.4 Building Trees     160
    11.5 Querying     164
    11.6 Navigation     168
    11.7 Tree Zipper     169
    11.8 Summary     172
Â
Chapter 12: Lazy Evaluation     173
    12.1 Delayed Evaluation of Arguments     173
    12.2 By-Name Arguments     174
    12.3 Control Abstraction     176
    12.4 Internal Domain-Specifc Languages     179
    12.5 Streams as Lazily Evaluated Lists     180
    12.6 Streams as Pipelines     182
    12.7 Streams as Infinite Data Structures     184
    12.8 Iterators     184
    12.9 Lists, Streams, Iterators, and Views     187
    12.10 Delayed Evaluation of Fields and Local Variables     190
    12.11 Illustration: Subset-Sum     191
    12.12 Summary     193
Â
Chapter 13: Handling Failures     195
    13.1 Exceptions and Special Values     195
    13.2 Using Option     197
    13.3 Using Try     198
    13.4 Using Either     199
    13.5 Higher-Order Functions and Pipelines     201
    13.6 Summary     204
Â
Chapter 14: Case Study: Trampolines     205
    14.1 Tail-Call Optimization     205
    14.2 Trampolines for Tail-Calls     206
    14.3 Tail-Call Optimization in Java     207
    14.4 Dealing with Non-Tail-Calls     209
    14.5 Summary     213
Â
A Brief Interlude     215
Â
Chapter 15: Types (and Related Concepts) Â Â Â Â Â 217
    15.1 Typing Strategies     217
    15.2 Types as Sets     222
    15.3 Types as Services     223
    15.4 Abstract Data Types     224
    15.5 Type Inference     225
    15.6 Subtypes     229
    15.7 Polymorphism     232
    15.8 Type Variance     235
    15.9 Type Bounds     241
    15.10 Type Classes     245
    15.11 Summary     250
Â
Part II. Concurrent Programming     253
Chapter 16: Concepts of Concurrent Programming     255
    16.1 Non-sequential Programs     255
    16.2 Concurrent Programming Concepts     258
    16.3 Summary     259
Â
Chapter 17: Threads and Nondeterminism     261
    17.1 Threads of Execution     261
    17.2 Creating Threads Using Lambda Expressions     263
    17.3 Nondeterministic Behavior of Multithreaded Programs     263
    17.4 Thread Termination     264
    17.5 Testing and Debugging Multithreaded Programs     266
    17.6 Summary     268
Â
Chapter 18: Atomicity and Locking     271
    18.1 Atomicity     271
    18.2 Non-atomic Operations     273
    18.3 Atomic Operations and Non-atomic Composition     274
    18.4 Locking     278
    18.5 Intrinsic Locks     279
    18.6 Choosing Locking Targets     281
    18.7 Summary     283
Â
Chapter 19: Thread-Safe Objects     285
    19.1 Immutable Objects     285
    19.2 Encapsulating Synchronization Policies     286
    19.3 Avoiding Reference Escape     288
    19.4 Public and Private Locks     289
    19.5 Leveraging Immutable Types     290
    19.6 Thread-Safety     293
    19.7 Summary     295
Â
Chapter 20: Case Study: Thread-Safe Queue     297
    20.1 Queues as Pairs of Lists     297
    20.2 Single Public Lock Implementation     298
    20.3 Single Private Lock Implementation     301
    20.4 Applying Lock Splitting     303
    20.5 Summary     305
Â
Chapter 21: Thread Pools     307
    21.1 Fire-and-Forget Asynchronous Execution     307
    21.2 Illustration: Parallel Server     309
    21.3 Different Types of Thread Pools     312
    21.4 Parallel Collections     314
    21.5 Summary     318
Â
Chapter 22: Synchronization     321
    22.1 Illustration of the Need for Synchronization     321
    22.2 Synchronizers     324
    22.3 Deadlocks     325
    22.4 Debugging Deadlocks with Thread Dumps     328
    22.5 The Java Memory Model     330
    22.6 Summary     335
Â
Chapter 23: Common Synchronizers     337
    23.1 Locks     337
    23.2 Latches and Barriers     339
    23.3 Semaphores     341
    23.4 Conditions     343
    23.5 Blocking Queues     349
    23.6 Summary     353
Â
Chapter 24: Case Study: Parallel Execution     355
    24.1 Sequential Reference Implementation     355
    24.2 One New Thread per Task     356
    24.3 Bounded Number of Threads     357
    24.4 Dedicated Thread Pool     359
    24.5 Shared Thread Pool     360
    24.6 Bounded Thread Pool     361
    24.7 Parallel Collections     362
    24.8 Asynchronous Task Submission Using Conditions     362
    24.9 Two-Semaphore Implementation     367
    24.10 Summary     368
Â
Chapter 25: Futures and Promises     369
    25.1 Functional Tasks     369
    25.2 Futures as Synchronizers     371
    25.3 Timeouts, Failures, and Cancellation     374
    25.4 Future Variants     375
    25.5 Promises     375
    25.6 Illustration: Thread-Safe Caching     377
    25.7 Summary     379
Â
Chapter 26: Functional-Concurrent Programming     381
    26.1 Correctness and Performance Issues with Blocking     381
    26.2 Callbacks     384
    26.3 Higher-Order Functions on Futures     385
    26.4 Function atMap on Futures     388
    26.5 Illustration: Parallel Server Revisited     390
    26.6 Functional-Concurrent Programming Patterns     393
    26.7 Summary     397
Â
Chapter 27: Minimizing Thread Blocking     399
    27.1 Atomic Operations     399
    27.2 Lock-Free Data Structures     402
    27.3 Fork/Join Pools     405
    27.4 Asynchronous Programming     406
    27.5 Actors     407
    27.6 Reactive Streams     411
    27.7 Non-blocking Synchronization     412
    27.8 Summary     414
Â
Chapter 28: Case Study: Parallel Strategies     417
    28.1 Problem Definition     417
    28.2 Sequential Implementation with Timeout     419
    28.3 Parallel Implementation Using invokeAny     420
    28.4 Parallel Implementation Using CompletionService     421
    28.5 Asynchronous Implementation with Scala Futures     422
    28.6 Asynchronous Implementation with CompletableFuture     426
    28.7 Caching Results from Strategies     427
    28.8 Summary     431
Â
Appendix A. Features of Java and Kotlin     433
    A.1 Functions in Java and Kotlin     433
    A.2 Immutability     436
    A.3 Pattern Matching and Algebraic Data Types     437
    A.4 Recursive Programming     439
    A.5 Higher-Order Functions     440
    A.6 Lazy Evaluation     446
    A.7 Handling Failures     449
    A.8 Types     451
    A.9 Threads     453
    A.10 Atomicity and Locking     454
    A.11 Thread-Safe Objects     455
    A.12 Thread Pools     457
    A.13 Synchronization     459
    A.14 Futures and Functional-Concurrent Programming     460
    A.15 Minimizing Thread Blocking     461
Â
Glossary     463
Index    465
