book

Functional Programming in Kotlin

Name: Functional Programming in Kotlin
ISBN: 9781617297168

by Runar Bjarnason, Marco Vermeulen, Paul Chiusano

September 2021

Intermediate to advanced

504 pages

12h 50m

English

Manning Publications

Audiobook available

Read now

Unlock full access

Functional Programming with Kotlin
Copyright
contents
front matter
forewordprefaceacknowledgmentsabout this bookWho should read this bookHow this book is organizedHow to read this bookAbout the codeliveBook discussion forum
Part 1. Introduction to functional programming
1 What is functional programming?
1.1 The benefits of FP: A simple example1.1.1 A program with side effects1.1.2 A functional solution: Removing the side effects1.2 Exactly what is a (pure) function?1.3 RT, purity, and the substitution model1.4 What lies aheadSummary
2 Getting started with functional programming in Kotlin
2.1 Higher-order functions: Passing functions to functions2.1.1 A short detour: Writing loops functionally2.1.2 Writing our first higher-order function2.2 Polymorphic functions: Abstracting over types2.2.1 An example of a polymorphic function2.2.2 Calling HOFs with anonymous functions2.3 Following types to implementationsSummary
3 Functional data structures
3.1 Defining functional data structures3.2 Working with functional data structures3.2.1 The “when” construct for matching by type3.2.2 The when construct as an alternative to if-else logic3.2.3 Pattern matching and how it differs from Kotlin matching3.3 Data sharing in functional data structures3.3.1 The efficiency of data sharing3.4 Recursion over lists and generalizing to HOFs3.4.1 More functions for working with lists3.4.2 Lists in the Kotlin standard library3.4.3 Inefficiency of assembling list functions from simpler components3.5 TreesSummary
4 Handling errors without exceptions
4.1 The problems with throwing exceptions4.2 Problematic alternatives to exceptions4.2.1 Sentinel value4.2.2 Supplied default value4.3 Encoding success conditions with Option4.3.1 Usage patterns for Option4.3.2 Option composition, lifting, and wrapping exception-oriented APIs4.3.3 For-comprehensions with Option4.4 Encoding success and failure conditions with Either4.4.1 For-comprehensions with EitherSummary
5 Strictness and laziness
5.1 Strict and non-strict functions5.2 An extended example: Lazy lists5.2.1 Memoizing streams and avoiding recomputation5.2.2 Helper functions for inspecting streams5.3 Separating program description from evaluation5.4 Producing infinite data streams through corecursive functions5.5 ConclusionSummary

6 Purely functional state
6.1 Generating random numbers using side effects6.2 Purely functional random number generation6.3 Making stateful APIs pure6.4 An implicit approach to passing state actions6.4.1 More power by combining state actions6.4.2 Recursive retries through nested state actions6.4.3 Applying the combinator API to the initial example6.5 A general state action data type6.6 Purely functional imperative programming6.7 ConclusionSummary
Part 2. Functional design and combinator libraries
7 Purely functional parallelism
7.1 Choosing data types and functions7.1.1 A data type for parallel computations7.1.2 Combining parallel computations to ensure concurrency7.1.3 Marking computations to be forked explicitly7.2 Picking a representation7.3 Refining the API with the end user in mind7.4 Reasoning about the API in terms of algebraic equations7.4.1 The law of mapping7.4.2 The law of forking7.4.3 Using actors for a non-blocking implementation7.5 Refining combinators to their most general formSummary
8 Property-based testing
8.1 A brief tour of property-based testing8.2 Choosing data types and functions8.2.1 Gathering initial snippets for a possible API8.2.2 Exploring the meaning and API of properties8.2.3 Discovering the meaning and API of generators8.2.4 Generators that depend on generated values8.2.5 Refining the property data type8.3 Test case minimization8.4 Using the library and improving the user experience8.4.1 Some simple examples8.4.2 Writing a test suite for parallel computations8.5 Generating higher-order functions and other possibilities8.6 The laws of generators8.7 ConclusionSummary
9 Parser combinators
9.1 Designing an algebra9.1.1 A parser to recognize single characters9.1.2 A parser to recognize entire strings9.1.3 A parser to recognize repetition9.2 One possible approach to designing an algebra9.2.1 Counting character repetition9.2.2 Slicing and nonempty repetition9.3 Handling context sensitivity9.4 Writing a JSON parser9.4.1 Defining expectations of a JSON parser9.4.2 Reviewing the JSON format9.4.3 A JSON parser9.5 Surfacing errors through reporting9.5.1 First attempt at representing errors9.5.2 Accumulating errors through error nesting9.5.3 Controlling branching and backtracking9.6 Implementing the algebra9.6.1 Building up the algebra implementation gradually9.6.2 Sequencing parsers after each other9.6.3 Capturing error messages through labeling parsers9.6.4 Recovering from error conditions and backtracking over them9.6.5 Propagating state through context-sensitive parsers9.7 ConclusionSummary
Part 3. Common structures in functional design
10 Monoids
10.1 What is a monoid?10.2 Folding lists with monoids10.3 Associativity and parallelism10.4 Example: Parallel parsing10.5 Foldable data structures10.6 Composing monoids10.6.1 Assembling more complex monoids10.6.2 Using composed monoids to fuse traversalsSummary
11 Monads and functors
11.1 Functors11.1.1 Defining the functor by generalizing the map function11.1.2 The importance of laws and their relation to the functor11.2 Monads: Generalizing the flatMap and unit functions11.2.1 Introducing the Monad interface11.3 Monadic combinators11.4 Monad laws11.4.1 The associative law11.4.2 Proving the associative law for a specific monad11.4.3 The left and right identity laws11.5 Just what is a monad?11.5.1 The identity monad11.5.2 The State monad and partial type applicationSummary
12 Applicative and traversable functors
12.1 Generalizing monads for reusability12.2 Applicatives as an alternative abstraction to the monad12.3 The difference between monads and applicative functors12.3.1 The Option applicative vs. the Option monad12.3.2 The Parser applicative vs. the Parser monad12.4 The advantages of applicative functors12.4.1 Not all applicative functors are monads12.5 Reasoning about programs through the applicative laws12.5.1 Laws of left and right identity12.5.2 Law of associativity12.5.3 Law of naturality12.6 Abstracting traverse and sequence using traversable functors12.7 Using Traversable to iteratively transform higher kinds12.7.1 From monoids to applicative functors12.7.2 Traversing collections while propagating state actions12.7.3 Combining traversable structures12.7.4 Traversal fusion for single pass efficiency12.7.5 Simultaneous traversal of nested traversable structures12.7.6 Pitfalls and workarounds for monad compositionSummary
Part 4. Effects and I/O
13 External effects and I/O
13.1 Factoring effects out of an effectful program13.2 Introducing the IO type to separate effectful code13.2.1 Handling input effects13.2.2 Benefits and drawbacks of the simple IO type13.3 Avoiding stack overflow errors by reification and trampolining13.3.1 Reifying control flow as data constructors13.3.2 Trampolining: A general solution to stack overflow13.4 A more nuanced IO type13.4.1 Reasonably priced monads13.4.2 A monad that supports only console I/O13.4.3 Testing console I/O by using pure interpreters13.5 Non-blocking and asynchronous I/O13.6 A general-purpose IO type13.6.1 The main program at the end of the universe13.7 Why the IO type is insufficient for streaming I/OSummary
14 Local effects and mutable state
14.1 State mutation is legal in pure functional code14.2 A data type to enforce scoping of side effects14.2.1 A domain-specific language for scoped mutation14.2.2 An algebra of mutable references14.2.3 Running mutable state actions14.2.4 The mutable array represented as a data type for the ST monad14.2.5 A purely functional in-place quicksort14.3 Purity is contextual14.3.1 Definition by example14.3.2 What counts as a side effect?Summary
15 Stream processing and incremental I/O
15.1 Problems with imperative I/O: An example15.2 Transforming streams with simple transducers15.2.1 Combinators for building stream transducers15.2.2 Combining multiple transducers by appending and composing15.2.3 Stream transducers for file processing15.3 An extensible process type for protocol parameterization15.3.1 Sources for stream emission15.3.2 Ensuring resource safety in stream transducers15.3.3 Applying transducers to a single-input stream15.3.4 Multiple input streams15.3.5 Sinks for output processing15.3.6 Hiding effects in effectful channels15.3.7 Dynamic resource allocation15.4 Application of stream transducers in the real worldSummaryFinal words
Appendix A. Exercise hints and tips
A.1 Chapter 3: Functional data structuresExercise 3.1Exercise 3.2Exercise 3.3Exercise 3.4Exercise 3.5Exercise 3.6Exercise 3.7Exercise 3.12Exercise 3.14Exercise 3.15Exercise 3.16Exercise 3.17Exercise 3.18Exercise 3.19Exercise 3.23Exercise 3.28A.2 Chapter 4: Handling errors without exceptionsExercise 4.3Exercise 4.4Exercise 4.5Exercise 4.6Exercise 4.7Exercise 4.8A.3 Chapter 5: Strictness and lazinessExercise 5.1Exercise 5.2Exercise 5.4Exercise 5.6Exercise 5.9Exercise 5.10Exercise 5.11Exercise 5.14Exercise 5.15Exercise 5.16A.4 Chapter 6: Purely functional stateExercise 6.2Exercise 6.5Exercise 6.6Exercise 6.7Exercise 6.8Exercise 6.9Exercise 6.10A.5 Chapter 7: Purely functional parallelismExercise 7.1Exercise 7.2Exercise 7.3Exercise 7.5Exercise 7.7A.6 Chapter 8: Property-based testingExercise 8.4Exercise 8.5Exercise 8.6Exercise 8.9Exercise 8.12Exercise 8.13Exercise 8.16A.7 Chapter 9: Parser combinatorsExercise 9.1Exercise 9.2Exercise 9.7Exercise 9.9Exercise 9.10Exercise 9.12A.8 Chapter 10: MonoidsExercise 10.2Exercise 10.3Exercise 10.4Exercise 10.5Exercise 10.6Exercise 10.7Exercise 10.8Exercise 10.9Exercise 10.13Exercise 10.19A.9 Chapter 11: Monads and functorsExercise 11.1Exercise 11.2Exercise 11.3Exercise 11.4Exercise 11.6Exercise 11.7Exercise 11.8Exercise 11.9Exercise 11.10Exercise 11.13Exercise 11.16Exercise 11.18Exercise 11.19A.10 Chapter 12: Applicative and traversable functorsExercise 12.2Exercise 12.3Exercise 12.5Exercise 12.6Exercise 12.7Exercise 12.8Exercise 12.9Exercise 12.10Exercise 12.11Exercise 12.12Exercise 12.13Exercise 12.15Exercise 12.16Exercise 12.17Exercise 12.18Exercise 12.19A.11 Chapter 13: External effects and I/OExercise 13.1Exercise 13.2Exercise 13.4A.12 Chapter 14: Local effects and mutable stateExercise 14.1Exercise 14.2Exercise 14.3A.13 Chapter 15: Stream processing and incremental I/OExercise 15.3Exercise 15.5Exercise 15.6Exercise 15.7Exercise 15.9Exercise 15.10Exercise 15.11Exercise 15.12
Appendix B. Exercise solutions
B.1 Before you proceed to the solutionsB.2 Getting started with functional programmingExercise 2.1Exercise 2.2Exercise 2.3Exercise 2.4Exercise 2.5B.3 Functional data structuresExercise 3.1Exercise 3.2Exercise 3.3Exercise 3.4Exercise 3.5Exercise 3.6Exercise 3.7Exercise 3.8Exercise 3.9Exercise 3.10Exercise 3.11Exercise 3.12 (Hard)Exercise 3.13Exercise 3.14 (Hard)Exercise 3.15Exercise 3.16Exercise 3.17Exercise 3.18Exercise 3.19Exercise 3.20Exercise 3.21Exercise 3.22Exercise 3.23Exercise 3.24Exercise 3.25Exercise 3.26Exercise 3.27Exercise 3.28B.4 Handling errors without exceptionsExercise 4.1Exercise 4.2Exercise 4.3Exercise 4.4Exercise 4.5Exercise 4.6Exercise 4.7Exercise 4.8B.5 Strictness and lazinessExercise 5.1Exercise 5.2Exercise 5.3Exercise 5.4Exercise 5.5Exercise 5.6 (Hard)Exercise 5.7Exercise 5.8Exercise 5.9Exercise 5.10Exercise 5.11Exercise 5.12Exercise 5.13Exercise 5.14 (Hard)Exercise 5.15Exercise 5.16 (Hard)B.6 Purely functional stateExercise 6.1Exercise 6.2Exercise 6.3Exercise 6.4Exercise 6.5Exercise 6.6Exercise 6.7Exercise 6.8Exercise 6.9Exercise 6.10Exercise 6.11B.7 Purely functional parallelismExercise 7.1Exercise 7.2Exercise 7.3Exercise 7.4Exercise 7.5Exercise 7.6Exercise 7.7 (Hard)Exercise 7.8 (Hard)Exercise 7.9 (Hard/Optional)Exercise 7.10Exercise 7.11Exercise 7.12Exercise 7.13B.8 Property-based testingExercise 8.1Exercise 8.2Exercise 8.3Exercise 8.4Exercise 8.5Exercise 8.6Exercise 8.7Exercise 8.8Exercise 8.9Exercise 8.10Exercise 8.11Exercise 8.12Exercise 8.13Exercise 8.14Exercise 8.15Exercise 8.16Exercise 8.17B.9 Parser combinatorsExercise 9.1Exercise 9.2 (Hard)Exercise 9.3Exercise 9.4Exercise 9.5Exercise 9.6Exercise 9.7Exercise 9.8Exercise 9.9 (Hard)Exercise 9.10Exercise 9.11Exercise 9.12Exercise 9.13Exercise 9.14B.10 MonoidsExercise 10.1Exercise 10.2Exercise 10.3Exercise 10.4Exercise 10.5Exercise 10.6Exercise 10.7Exercise 10.8 (Hard/Optional)Exercise 10.9 (Hard/Optional)Exercise 10.10Exercise 10.11Exercise 10.12Exercise 10.13Exercise 10.14Exercise 10.15Exercise 10.16Exercise 10.17Exercise 10.18Exercise 10.19B.11 Monads and functorsExercise 11.1Exercise 11.2Exercise 11.3Exercise 11.4Exercise 11.5Exercise 11.6 (Hard)Exercise 11.7Exercise 11.8 (Hard)Exercise 11.9Exercise 11.10Exercise 11.11Exercise 11.12Exercise 11.13 (Hard/Optional)Exercise 11.14 (Hard/Optional)Exercise 11.15 (Hard/Optional)Exercise 11.16Exercise 11.17Exercise 11.18Exercise 11.19 (Hard)B.12 Applicative and traversable functorsExercise 12.1Exercise 12.2 (Hard)Exercise 12.3Exercise 12.4Exercise 12.5Exercise 12.6Exercise 12.7 (Hard)Exercise 12.8Exercise 12.9Exercise 12.10Exercise 12.11Exercise 12.12 (Hard)Exercise 12.13 (Hard)Exercise 12.14Exercise 12.15Exercise 12.16Exercise 12.17Exercise 12.18 (Hard)Exercise 12.19 (Hard/Optional)B.13 External effects and I/OExercise 13.1Exercise 13.2Exercise 13.3 (Hard)Exercise 13.4 (Hard/Optional)B.14 Local effects and mutable stateExercise 14.1Exercise 14.2Exercise 14.3B.15 Stream processing and incremental I/OExercise 15.1Exercise 15.2Exercise 15.3Exercise 15.4Exercise 15.5 (Hard)Exercise 15.6Exercise 15.7 (Optional)Exercise 15.8Exercise 15.9 (Optional)Exercise 15.10Exercise 15.11Exercise 15.12
Appendix C. Higher-kinded types
C.1 A compiler workaroundC.2 Partially applied type constructorsC.3 Boilerplate code generation with Arrow Meta
Appendix D. Type classes
D.1 PolymorphismD.2 Using type classes to express ad hoc polymorphismD.3 Type classes foster a separation of concerns
index

Content preview from Functional Programming in Kotlin

3 Functional data structures

This chapter covers

Defining functional data structures using algebraic data types
Writing branching logic in a single expression
Sharing data using functional data structures
Using list recursion and generalizing to HOFs
Writing and generalizing pure functions
Implementing List and Tree

We said in chapter 1 that functional programs don’t update variables or modify mutable data structures. The emphasis on keeping variables immutable raises pressing questions: what sort of data structures can we use in functional programming, how do we define them in Kotlin, and how do we operate on them?

This chapter teaches the concept of functional data structures by writing our own implementations of a singly linked list and ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9781617297168Publisher Support Publisher Website

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Functional Programming in Kotlin

by Runar Bjarnason, Marco Vermeulen, Paul Chiusano

3 Functional data structures

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.