Functional Programming in Scala

**Summary** __Functional Programming in Scala__ is a serious tutorial for programmers looking to learn FP and apply it to the everyday business of coding. The book guides readers from basic techniques to advanced topics in a logical, concise, and clear progression. In it, you'll find concrete examples and exercises that open up the world of functional programming. Purchase of the print book includes a free eBook in PDF, Kindle, and ePub formats from Manning Publications. **About the Technology** Functional programming (FP) is a style of software development emphasizing functions that don't depend on program state. Functional code is easier to test and reuse, simpler to parallelize, and less prone to bugs than other code. Scala is an emerging JVM language that offers strong support for FP. Its familiar syntax and transparent interoperability with Java make Scala a great place to start learning FP. **About the Book** Functional Programming in Scala is a serious tutorial for programmers looking to learn FP and apply it to their everyday work. The book guides readers from basic techniques to advanced topics in a logical, concise, and clear progression. In it, you'll find concrete examples and exercises that open up the world of functional programming. This book assumes no prior experience with functional programming. Some prior exposure to Scala or Java is helpful. **What's Inside** * Functional programming concepts * The whys and hows of FP * How to write multicore programs * Exercises and checks for understanding **About the Authors**Paul Chiusano and Rúnar Bjarnason are recognized experts in functional programming with Scala and are core contributors to the Scalaz library **Table of Contents** PART 1 INTRODUCTION TO FUNCTIONAL PROGRAMMING2. What is functional programming? 3. Getting started with functional programming in Scala 4. Functional data structures 5. Handling errors without exceptions 6. Strictness and laziness 7. Purely functional state PART 2 FUNCTIONAL DESIGN AND COMBINATOR LIBRARIES9. Purely functional parallelism 10. Property-based testing 11. Parser combinators PART 3 COMMON STRUCTURES IN FUNCTIONAL DESIGN13. Monoids 14. Monads 15. Applicative and traversable functors PART 4 EFFECTS AND I/O17. External effects and I/O 18. Local effects and mutable state 19. Stream processing and incremental I/O brief contents 6 contents 8 foreword 14 preface 16 acknowledgments 17 about this book 18 How this book is structured 18 Audience 19 How to read this book 19 Code conventions and downloads 20 Setting expectations 21 Author Online 21 Part 1 Introduction to functional programming 22 1 What is functional programming? 24 1.1 The benefits of FP: a simple example 25 1.1.1 A program with side effects 25 1.1.2 A functional solution: removing the side effects 27 1.2 Exactly what is a (pure) function? 30 1.3 Referential transparency, purity, and the substitution model 31 1.4 Summary 34 2 Getting started with functional programming in Scala 35 2.1 Introducing Scala the language: an example 36 2.2 Running our program 38 2.3 Modules, objects, and namespaces 39 2.4 Higher-order functions: passing functions to functions 40 2.4.1 A short detour: writing loops functionally 41 2.4.2 Writing our first higher-order function 42 2.5 Polymorphic functions: abstracting over types 43 2.5.1 An example of a polymorphic function 44 2.5.2 Calling HOFs with anonymous functions 45 2.6 Following types to implementations 46 2.7 Summary 49 3 Functional data structures 50 3.1 Defining functional data structures 50 3.2 Pattern matching 53 3.3 Data sharing in functional data structures 56 3.3.1 The efficiency of data sharing 57 3.3.2 Improving type inference for higher-order functions 58 3.4 Recursion over lists and generalizing to higher-order functions 59 3.4.1 More functions for working with lists 62 3.4.2 Loss of efficiency when assembling list functions from simpler components 65 3.5 Trees 65 3.6 Summary 68 4 Handling errors without exceptions 69 4.1 The good and bad aspects of exceptions 69 4.2 Possible alternatives to exceptions 71 4.3 The Option data type 73 4.3.1 Usage patterns for Option 74 4.3.2 Option composition, lifting, and wrapping exception-oriented APIs 77 4.4 The Either data type 81 4.5 Summary 84 5 Strictness and laziness 85 5.1 Strict and non-strict functions 86 5.2 An extended example: lazy lists 89 5.2.1 Memoizing streams and avoiding recomputation 90 5.2.2 Helper functions for inspecting streams 90 5.3 Separating program description from evaluation 91 5.4 Infinite streams and corecursion 94 5.5 Summary 98 6 Purely functional state 99 6.1 Generating random numbers using side effects 99 6.2 Purely functional random number generation 101 6.3 Making stateful APIs pure 102 6.4 A better API for state actions 105 6.4.1 Combining state actions 106 6.4.2 Nesting state actions 107 6.5 A general state action data type 108 6.6 Purely functional imperative programming 109 6.7 Summary 112 Part 2 Functional design and combinator libraries 114 7 Purely functional parallelism 116 7.1 Choosing data types and functions 117 7.1.1 A data type for parallel computations 118 7.1.2 Combining parallel computations 121 7.1.3 Explicit forking 123 7.2 Picking a representation 125 7.3 Refining the API 126 7.4 The algebra of an API 131 7.4.1 The law of mapping 131 7.4.2 The law of forking 133 7.4.3 Breaking the law: a subtle bug 134 7.4.4 A fully non-blocking Par implementation using actors 136 7.5 Refining combinators to their most general form 141 7.6 Summary 144 8 Property-based testing 145 8.1 A brief tour of property-based testing 145 8.2 Choosing data types and functions 148 8.2.1 Initial snippets of an API 148 8.2.2 The meaning and API of properties 149 8.2.3 The meaning and API of generators 151 8.2.4 Generators that depend on generated values 152 8.2.5 Refining the Prop data type 153 8.3 Test case minimization 155 8.4 Using the library and improving its usability 157 8.4.1 Some simple examples 158 8.4.2 Writing a test suite for parallel computations 159 8.5 Testing higher-order functions and future directions 163 8.6 The laws of generators 165 8.7 Summary 165 9 Parser combinators 167 9.1 Designing an algebra, first 168 9.2 A possible algebra 173 9.2.1 Slicing and nonempty repetition 175 9.3 Handling context sensitivity 177 9.4 Writing a JSON parser 179 9.4.1 The JSON format 179 9.4.2 A JSON parser 180 9.5 Error reporting 181 9.5.1 A possible design 182 9.5.2 Error nesting 183 9.5.3 Controlling branching and backtracking 184 9.6 Implementing the algebra 186 9.6.1 One possible implementation 187 9.6.2 Sequencing parsers 187 9.6.3 Labeling parsers 188 9.6.4 Failover and backtracking 189 9.6.5 Context-sensitive parsing 190 9.7 Summary 192 Part 3 Common structures in functional design 194 10 Monoids 196 10.1 What is a monoid? 196 10.2 Folding lists with monoids 199 10.3 Associativity and parallelism 200 10.4 Example: Parallel parsing 202 10.5 Foldable data structures 204 10.6 Composing monoids 205 10.6.1 Assembling more complex monoids 206 10.6.2 Using composed monoids to fuse traversals 207 10.7 Summary 207 11 Monads 208 11.1 Functors: generalizing the map function 208 11.1.1 Functor laws 210 11.2 Monads: generalizing the flatMap and unit functions 211 11.2.1 The Monad trait 212 11.3 Monadic combinators 214 11.4 Monad laws 215 11.4.1 The associative law 215 11.4.2 Proving the associative law for a specific monad 217 11.4.3 The identity laws 218 11.5 Just what is a monad? 219 11.5.1 The identity monad 220 11.5.2 The State monad and partial type application 221 11.6 Summary 225 12 Applicative and traversable functors 226 12.1 Generalizing monads 226 12.2 The Applicative trait 227 12.3 The difference between monads and applicative functors 229 12.3.1 The Option applicative versus the Option monad 230 12.3.2 The Parser applicative versus the Parser monad 231 12.4 The advantages of applicative functors 232 12.4.1 Not all applicative functors are monads 232 12.5 The applicative laws 235 12.5.1 Left and right identity 235 12.5.2 Associativity 236 12.5.3 Naturality of product 237 12.6 Traversable functors 239 12.7 Uses of Traverse 240 12.7.1 From monoids to applicative functors 241 12.7.2 Traversals with State 242 12.7.3 Combining traversable structures 244 12.7.4 Traversal fusion 245 12.7.5 Nested traversals 245 12.7.6 Monad composition 246 12.8 Summary 247 Part 4 Effects and I/O 248 13 External effects and I/O 250 13.1 Factoring effects 250 13.2 A simple IO type 252 13.2.1 Handling input effects 253 13.2.2 Benefits and drawbacks of the simple IO type 256 13.3 Avoiding the StackOverflowError 258 13.3.1 Reifying control flow as data constructors 258 13.3.2 Trampolining: a general solution to stack overflow 260 13.4 A more nuanced IO type 262 13.4.1 Reasonably priced monads 263 13.4.2 A monad that supports only console I/O 264 13.4.3 Pure interpreters 267 13.5 Non-blocking and asynchronous I/O 268 13.6 A general-purpose IO type 271 13.6.1 The main program at the end of the universe 271 13.7 Why the IO type is insufficient for streaming I/O 272 13.8 Summary 274 14 Local effects and mutable state 275 14.1 Purely functional mutable state 275 14.2 A data type to enforce scoping of side effects 277 14.2.1 A little language for scoped mutation 277 14.2.2 An algebra of mutable references 279 14.2.3 Running mutable state actions 280 14.2.4 Mutable arrays 283 14.2.5 A purely functional in-place quicksort 284 14.3 Purity is contextual 285 14.3.1 What counts as a side effect? 287 14.4 Summary 288 15 Stream processing and incremental I/O 289 15.1 Problems with imperative I/O: an example 289 15.2 Simple stream transducers 292 15.2.1 Creating processes 293 15.2.2 Composing and appending processes 296 15.2.3 Processing files 299 15.3 An extensible process type 299 15.3.1 Sources 302 15.3.2 Ensuring resource safety 304 15.3.3 Single-input processes 306 15.3.4 Multiple input streams 308 15.3.5 Sinks 311 15.3.6 Effectful channels 312 15.3.7 Dynamic resource allocation 312 15.4 Applications 313 15.5 Summary 314 index 316 Symbols 316 A 316 B 316 C 316 D 317 E 317 F 317 G 318 H 318 I 318 J 318 K 318 L 318 M 319 N 319 O 319 P 319 Q 320 R 320 S 320 T 321 U 321 V 321 W 321 Y 321 Functional Programming in Scala is a serious tutorial for programmers looking to learn FP and apply it to the everyday business of coding. The book guides readers from basic techniques to advanced topics in a logical, concise, and clear progression. In it, you'll find concrete examples and exercises that open up the world of functional programming. Functional Programming in Scala is a serious tutorial for programmers looking to learn FP and apply it to their everyday work. The book guides readers from basic techniques to advanced topics in a logical, concise, and clear progression. In it, you'll find concrete examples and exercises that open up the world of functional programming. Summary About the Technology Functional programming (FP) is a style of software development emphasizing functions that don't depend on program state. Functional code is easier to test and reuse, simpler to parallelize, and less prone to bugs than other code. Scala is an emerging JVM language that offers strong support for FP. Its familiar syntax and transparent interoperability with Java make Scala a great place to start learning FP. About the Book This book assumes no prior experience with functional programming. Some prior exposure to Scala or Java is helpful. What's Inside Functional programming concepts The whys and hows of FP How to write multicore programs Exercises and checks for understanding About the Authors Paul Chiusano and Rúnar Bjarnason are recognized experts in functional programming with Scala and are core contributors to the Scalaz library Functional programming (FP) is a programming style emphasizing functions that return consistent and predictable results regardless of a program's state. As a result, functional code is easier to test and reuse, simpler to parallelize, and less prone to bugs. Scala is an emerging JVM language that offers strong support for FP. Its familiar syntax and transparent interoperability with existing Java libraries make Scala a great place to start learning FP. Functional Programming in Scala is a serious tutorial for programmers looking to learn FP and apply it to the everyday business of coding. The book guides readers from basic techniques to advanced topics in a logical, concise, and clear progression. In it, they'll find concrete examples and exercises that open up the world of functional programming. Purchase of the print book comes with an offer of a free PDF, ePub, and Kindle eBook from Manning. Also available is all code from the book.