We said in the introduction that functional programs don’t update variables or modify mutable data structures. This raises pressing questions: What sort of data structures can we use in functional programming? How do we define them in Scala? And how do we operate on them? In this chapter, we’ll learn the concept of functional data structures and how to work with them. We’ll use this as an opportunity to introduce how data types are defined in functional programming, learn about the related technique of pattern matching, and get practice writing and generalizing pure functions.
This chapter has many exercises, particularly dealing with writing and generalizing pure functions. Some of these exercises may be challenging; the answers are provided, but try to work through each exercise before looking at the answer, as these techniques require practice to fully grasp. You can also consult our GitHub site (https://github.com/fpinscala/fpinscala), which provides a build environment for the exercises and answers.