Functional Programming in Kotlin

Functional Programming in Kotlin
contents
foreword
preface
acknowledgments
about this book
	Who should read this book
	How this book is organized
	How to read this book
	About the code
	liveBook discussion forum
Part 1—Introduction to functional programming
	1 What is functional programming?
		1.1 The benefits of FP: A simple example
			1.1.1 A program with side effects
			1.1.2 A functional solution: Removing the side effects
		1.2 Exactly what is a (pure) function?
		1.3 RT, purity, and the substitution model
		1.4 What lies ahead
		Summary
	2 Getting started with functional programming in Kotlin
		2.1 Higher-order functions: Passing functions to functions
			2.1.1 A short detour: Writing loops functionally
			2.1.2 Writing our first higher-order function
		2.2 Polymorphic functions: Abstracting over types
			2.2.1 An example of a polymorphic function
			2.2.2 Calling HOFs with anonymous functions
		2.3 Following types to implementations
		Summary
	3 Functional data structures
		3.1 Defining functional data structures
		3.2 Working with functional data structures
			3.2.1 The “when” construct for matching by type
			3.2.2 The when construct as an alternative to if-else logic
			3.2.3 Pattern matching and how it differs from Kotlin matching
		3.3 Data sharing in functional data structures
			3.3.1 The efficiency of data sharing
		3.4 Recursion over lists and generalizing to HOFs
			3.4.1 More functions for working with lists
			3.4.2 Lists in the Kotlin standard library
			3.4.3 Inefficiency of assembling list functions from simpler components
		3.5 Trees
		Summary
	4 Handling errors without exceptions
		4.1 The problems with throwing exceptions
		4.2 Problematic alternatives to exceptions
			4.2.1 Sentinel value
			4.2.2 Supplied default value
		4.3 Encoding success conditions with Option
			4.3.1 Usage patterns for Option
			4.3.2 Option composition, lifting, and wrapping exception-oriented APIs
			4.3.3 For-comprehensions with Option
		4.4 Encoding success and failure conditions with Either
			4.4.1 For-comprehensions with Either
		Summary
	5 Strictness and laziness
		5.1 Strict and non-strict functions
		5.2 An extended example: Lazy lists
			5.2.1 Memoizing streams and avoiding recomputation
			5.2.2 Helper functions for inspecting streams
		5.3 Separating program description from evaluation
		5.4 Producing infinite data streams through corecursive functions
		5.5 Conclusion
		Summary
	6 Purely functional state
		6.1 Generating random numbers using side effects
		6.2 Purely functional random number generation
		6.3 Making stateful APIs pure
		6.4 An implicit approach to passing state actions
			6.4.1 More power by combining state actions
			6.4.2 Recursive retries through nested state actions
			6.4.3 Applying the combinator API to the initial example
		6.5 A general state action data type
		6.6 Purely functional imperative programming
		6.7 Conclusion
		Summary
Part 2—Functional design and combinator libraries
	7 Purely functional parallelism
		7.1 Choosing data types and functions
			7.1.1 A data type for parallel computations
			7.1.2 Combining parallel computations to ensure concurrency
			7.1.3 Marking computations to be forked explicitly
		7.2 Picking a representation
		7.3 Refining the API with the end user in mind
		7.4 Reasoning about the API in terms of algebraic equations
			7.4.1 The law of mapping
			7.4.2 The law of forking
			7.4.3 Using actors for a non-blocking implementation
		7.5 Refining combinators to their most general form
		Summary
	8 Property-based testing
		8.1 A brief tour of property-based testing
		8.2 Choosing data types and functions
			8.2.1 Gathering initial snippets for a possible API
			8.2.2 Exploring the meaning and API of properties
			8.2.3 Discovering the meaning and API of generators
			8.2.4 Generators that depend on generated values
			8.2.5 Refining the property data type
		8.3 Test case minimization
		8.4 Using the library and improving the user experience
			8.4.1 Some simple examples
			8.4.2 Writing a test suite for parallel computations
		8.5 Generating higher-order functions and other possibilities
		8.6 The laws of generators
		8.7 Conclusion
		Summary
	9 Parser combinators
		9.1 Designing an algebra
			9.1.1 A parser to recognize single characters
			9.1.2 A parser to recognize entire strings
			9.1.3 A parser to recognize repetition
		9.2 One possible approach to designing an algebra
			9.2.1 Counting character repetition
			9.2.2 Slicing and nonempty repetition
		9.3 Handling context sensitivity
		9.4 Writing a JSON parser
			9.4.1 Defining expectations of a JSON parser
			9.4.2 Reviewing the JSON format
			9.4.3 A JSON parser
		9.5 Surfacing errors through reporting
			9.5.1 First attempt at representing errors
			9.5.2 Accumulating errors through error nesting
			9.5.3 Controlling branching and backtracking
		9.6 Implementing the algebra
			9.6.1 Building up the algebra implementation gradually
			9.6.2 Sequencing parsers after each other
			9.6.3 Capturing error messages through labeling parsers
			9.6.4 Recovering from error conditions and backtracking over them
			9.6.5 Propagating state through context-sensitive parsers
		9.7 Conclusion
		Summary
Part 3—Common structures in functional design
	10 Monoids
		10.1 What is a monoid?
		10.2 Folding lists with monoids
		10.3 Associativity and parallelism
		10.4 Example: Parallel parsing
		10.5 Foldable data structures
		10.6 Composing monoids
			10.6.1 Assembling more complex monoids
			10.6.2 Using composed monoids to fuse traversals
		Summary
	11 Monads and functors
		11.1 Functors
			11.1.1 Defining the functor by generalizing the map function
			11.1.2 The importance of laws and their relation to the functor
		11.2 Monads: Generalizing the flatMap and unit functions
			11.2.1 Introducing the Monad interface
		11.3 Monadic combinators
		11.4 Monad laws
			11.4.1 The associative law
			11.4.2 Proving the associative law for a specific monad
			11.4.3 The left and right identity laws
		11.5 Just what is a monad?
			11.5.1 The identity monad
			11.5.2 The State monad and partial type application
		Summary
	12 Applicative and traversable functors
		12.1 Generalizing monads for reusability
		12.2 Applicatives as an alternative abstraction to the monad
		12.3 The difference between monads and applicative functors
			12.3.1 The Option applicative vs. the Option monad
			12.3.2 The Parser applicative vs. the Parser monad
		12.4 The advantages of applicative functors
			12.4.1 Not all applicative functors are monads
		12.5 Reasoning about programs through the applicative laws
			12.5.1 Laws of left and right identity
			12.5.2 Law of associativity
			12.5.3 Law of naturality
		12.6 Abstracting traverse and sequence using traversable functors
		12.7 Using Traversable to iteratively transform higher kinds
			12.7.1 From monoids to applicative functors
			12.7.2 Traversing collections while propagating state actions
			12.7.3 Combining traversable structures
			12.7.4 Traversal fusion for single pass efficiency
			12.7.5 Simultaneous traversal of nested traversable structures
			12.7.6 Pitfalls and workarounds for monad composition
		Summary
Part 4—Effects and I/O
	13 External effects and I/O
		13.1 Factoring effects out of an effectful program
		13.2 Introducing the IO type to separate effectful code
			13.2.1 Handling input effects
			13.2.2 Benefits and drawbacks of the simple IO type
		13.3 Avoiding stack overflow errors by reification and trampolining
			13.3.1 Reifying control flow as data constructors
			13.3.2 Trampolining: A general solution to stack overflow
		13.4 A more nuanced IO type
			13.4.1 Reasonably priced monads
			13.4.2 A monad that supports only console I/O
			13.4.3 Testing console I/O by using pure interpreters
		13.5 Non-blocking and asynchronous I/O
		13.6 A general-purpose IO type
			13.6.1 The main program at the end of the universe
		13.7 Why the IO type is insufficient for streaming I/O
		Summary
	14 Local effects and mutable state
		14.1 State mutation is legal in pure functional code
		14.2 A data type to enforce scoping of side effects
			14.2.1 A domain-specific language for scoped mutation
			14.2.2 An algebra of mutable references
			14.2.3 Running mutable state actions
			14.2.4 The mutable array represented as a data type for the ST monad
			14.2.5 A purely functional in-place quicksort
		14.3 Purity is contextual
			14.3.1 Definition by example
			14.3.2 What counts as a side effect?
		Summary
	15 Stream processing and incremental I/O
		15.1 Problems with imperative I/O: An example
		15.2 Transforming streams with simple transducers
			15.2.1 Combinators for building stream transducers
			15.2.2 Combining multiple transducers by appending and composing
			15.2.3 Stream transducers for file processing
		15.3 An extensible process type for protocol parameterization
			15.3.1 Sources for stream emission
			15.3.2 Ensuring resource safety in stream transducers
			15.3.3 Applying transducers to a single-input stream
			15.3.4 Multiple input streams
			15.3.5 Sinks for output processing
			15.3.6 Hiding effects in effectful channels
			15.3.7 Dynamic resource allocation
		15.4 Application of stream transducers in the real world
		Summary
		Final words
Appendix A—Exercise hints and tips
	A.1 Chapter 3: Functional data structures
		Exercise 3.1
		Exercise 3.2
		Exercise 3.3
		Exercise 3.4
		Exercise 3.5
		Exercise 3.6
		Exercise 3.7
		Exercise 3.12
		Exercise 3.14
		Exercise 3.15
		Exercise 3.16
		Exercise 3.17
		Exercise 3.18
		Exercise 3.19
		Exercise 3.23
		Exercise 3.28
	A.2 Chapter 4: Handling errors without exceptions
		Exercise 4.3
		Exercise 4.4
		Exercise 4.5
		Exercise 4.6
		Exercise 4.7
		Exercise 4.8
	A.3 Chapter 5: Strictness and laziness
		Exercise 5.1
		Exercise 5.2
		Exercise 5.4
		Exercise 5.6
		Exercise 5.9
		Exercise 5.10
		Exercise 5.11
		Exercise 5.14
		Exercise 5.15
		Exercise 5.16
	A.4 Chapter 6: Purely functional state
		Exercise 6.2
		Exercise 6.5
		Exercise 6.6
		Exercise 6.7
		Exercise 6.8
		Exercise 6.9
		Exercise 6.10
	A.5 Chapter 7: Purely functional parallelism
		Exercise 7.1
		Exercise 7.2
		Exercise 7.3
		Exercise 7.5
		Exercise 7.7
	A.6 Chapter 8: Property-based testing
		Exercise 8.4
		Exercise 8.5
		Exercise 8.6
		Exercise 8.9
		Exercise 8.12
		Exercise 8.13
		Exercise 8.16
	A.7 Chapter 9: Parser combinators
		Exercise 9.1
		Exercise 9.2
		Exercise 9.7
		Exercise 9.9
		Exercise 9.10
		Exercise 9.12
	A.8 Chapter 10: Monoids
		Exercise 10.2
		Exercise 10.3
		Exercise 10.4
		Exercise 10.5
		Exercise 10.6
		Exercise 10.7
		Exercise 10.8
		Exercise 10.9
		Exercise 10.13
		Exercise 10.19
	A.9 Chapter 11: Monads and functors
		Exercise 11.1
		Exercise 11.2
		Exercise 11.3
		Exercise 11.4
		Exercise 11.6
		Exercise 11.7
		Exercise 11.8
		Exercise 11.9
		Exercise 11.10
		Exercise 11.13
		Exercise 11.16
		Exercise 11.18
		Exercise 11.19
	A.10 Chapter 12: Applicative and traversable functors
		Exercise 12.2
		Exercise 12.3
		Exercise 12.5
		Exercise 12.6
		Exercise 12.7
		Exercise 12.8
		Exercise 12.9
		Exercise 12.10
		Exercise 12.11
		Exercise 12.12
		Exercise 12.13
		Exercise 12.15
		Exercise 12.16
		Exercise 12.17
		Exercise 12.18
		Exercise 12.19
	A.11 Chapter 13: External effects and I/O
		Exercise 13.1
		Exercise 13.2
		Exercise 13.4
	A.12 Chapter 14: Local effects and mutable state
		Exercise 14.1
		Exercise 14.2
		Exercise 14.3
	A.13 Chapter 15: Stream processing and incremental I/O
		Exercise 15.3
		Exercise 15.5
		Exercise 15.6
		Exercise 15.7
		Exercise 15.9
		Exercise 15.10
		Exercise 15.11
		Exercise 15.12
Appendix B—Exercise solutions
	B.1 Before you proceed to the solutions
	B.2 Getting started with functional programming
		Exercise 2.1
		Exercise 2.2
		Exercise 2.3
		Exercise 2.4
		Exercise 2.5
	B.3 Functional data structures
		Exercise 3.1
		Exercise 3.2
		Exercise 3.3
		Exercise 3.4
		Exercise 3.5
		Exercise 3.6
		Exercise 3.7
		Exercise 3.8
		Exercise 3.9
		Exercise 3.10
		Exercise 3.11
		Exercise 3.12 (Hard)
		Exercise 3.13
		Exercise 3.14 (Hard)
		Exercise 3.15
		Exercise 3.16
		Exercise 3.17
		Exercise 3.18
		Exercise 3.19
		Exercise 3.20
		Exercise 3.21
		Exercise 3.22
		Exercise 3.23
		Exercise 3.24
		Exercise 3.25
		Exercise 3.26
		Exercise 3.27
		Exercise 3.28
	B.4 Handling errors without exceptions
		Exercise 4.1
		Exercise 4.2
		Exercise 4.3
		Exercise 4.4
		Exercise 4.5
		Exercise 4.6
		Exercise 4.7
		Exercise 4.8
	B.5 Strictness and laziness
		Exercise 5.1
		Exercise 5.2
		Exercise 5.3
		Exercise 5.4
		Exercise 5.5
		Exercise 5.6 (Hard)
		Exercise 5.7
		Exercise 5.8
		Exercise 5.9
		Exercise 5.10
		Exercise 5.11
		Exercise 5.12
		Exercise 5.13
		Exercise 5.14 (Hard)
		Exercise 5.15
		Exercise 5.16 (Hard)
	B.6 Purely functional state
		Exercise 6.1
		Exercise 6.2
		Exercise 6.3
		Exercise 6.4
		Exercise 6.5
		Exercise 6.6
		Exercise 6.7
		Exercise 6.8
		Exercise 6.9
		Exercise 6.10
		Exercise 6.11
	B.7 Purely functional parallelism
		Exercise 7.1
		Exercise 7.2
		Exercise 7.3
		Exercise 7.4
		Exercise 7.5
		Exercise 7.6
		Exercise 7.7 (Hard)
		Exercise 7.8 (Hard)
		Exercise 7.9 (Hard/Optional)
		Exercise 7.10
		Exercise 7.11
		Exercise 7.12
		Exercise 7.13
	B.8 Property-based testing
		Exercise 8.1
		Exercise 8.2
		Exercise 8.3
		Exercise 8.4
		Exercise 8.5
		Exercise 8.6
		Exercise 8.7
		Exercise 8.8
		Exercise 8.9
		Exercise 8.10
		Exercise 8.11
		Exercise 8.12
		Exercise 8.13
		Exercise 8.14
		Exercise 8.15
		Exercise 8.16
		Exercise 8.17
	B.9 Parser combinators
		Exercise 9.1
		Exercise 9.2 (Hard)
		Exercise 9.3
		Exercise 9.4
		Exercise 9.5
		Exercise 9.6
		Exercise 9.7
		Exercise 9.8
		Exercise 9.9 (Hard)
		Exercise 9.10
		Exercise 9.11
		Exercise 9.12
		Exercise 9.13
		Exercise 9.14
	B.10 Monoids
		Exercise 10.1
		Exercise 10.2
		Exercise 10.3
		Exercise 10.4
		Exercise 10.5
		Exercise 10.6
		Exercise 10.7
		Exercise 10.8 (Hard/Optional)
		Exercise 10.9 (Hard/Optional)
		Exercise 10.10
		Exercise 10.11
		Exercise 10.12
		Exercise 10.13
		Exercise 10.14
		Exercise 10.15
		Exercise 10.16
		Exercise 10.17
		Exercise 10.18
		Exercise 10.19
	B.11 Monads and functors
		Exercise 11.1
		Exercise 11.2
		Exercise 11.3
		Exercise 11.4
		Exercise 11.5
		Exercise 11.6 (Hard)
		Exercise 11.7
		Exercise 11.8 (Hard)
		Exercise 11.9
		Exercise 11.10
		Exercise 11.11
		Exercise 11.12
		Exercise 11.13 (Hard/Optional)
		Exercise 11.14 (Hard/Optional)
		Exercise 11.15 (Hard/Optional)
		Exercise 11.16
		Exercise 11.17
		Exercise 11.18
		Exercise 11.19 (Hard)
	B.12 Applicative and traversable functors
		Exercise 12.1
		Exercise 12.2 (Hard)
		Exercise 12.3
		Exercise 12.4
		Exercise 12.5
		Exercise 12.6
		Exercise 12.7 (Hard)
		Exercise 12.8
		Exercise 12.9
		Exercise 12.10
		Exercise 12.11
		Exercise 12.12 (Hard)
		Exercise 12.13 (Hard)
		Exercise 12.14
		Exercise 12.15
		Exercise 12.16
		Exercise 12.17
		Exercise 12.18 (Hard)
		Exercise 12.19 (Hard/Optional)
	B.13 External effects and I/O
		Exercise 13.1
		Exercise 13.2
		Exercise 13.3 (Hard)
		Exercise 13.4 (Hard/Optional)
	B.14 Local effects and mutable state
		Exercise 14.1
		Exercise 14.2
		Exercise 14.3
	B.15 Stream processing and incremental I/O
		Exercise 15.1
		Exercise 15.2
		Exercise 15.3
		Exercise 15.4
		Exercise 15.5 (Hard)
		Exercise 15.6
		Exercise 15.7 (Optional)
		Exercise 15.8
		Exercise 15.9 (Optional)
		Exercise 15.10
		Exercise 15.11
		Exercise 15.12
Appendix C—Higher-kinded types
	C.1 A compiler workaround
	C.2 Partially applied type constructors
	C.3 Boilerplate code generation with Arrow Meta
Appendix D—Type classes
	D.1 Polymorphism
	D.2 Using type classes to express ad hoc polymorphism
	D.3 Type classes foster a separation of concerns
index
	Symbols
	A
	B
	C
	D
	E
	F
	G
	H
	I
	J
	K
	L
	M
	N
	O
	P
	Q
	R
	S
	T
	U
	V
	W
	Y
	Z