Chapter 3. Data Structures and Algorithms
This chapter looks at how the principles of functional programming influence the design of data structures and algorithms. We won’t have the space to study either in depth, but we’ll learn some universal principles by studying a few important examples.
Functional languages provide a core set of common data structures with combinator operations that are very powerful for working with data. Functional algorithms emphasize declarative structure, immutable values, and side-effect-free functions.
This chapter is dense with details and it might be hard to digest on a first reading. However, the ideas discussed here are the basis for functional programming’s elegance, conciseness, and composability.
Let’s start with an in-depth discussion of lists, followed by a brief discussion of maps.
The linked list has been
the central data structure in functional languages since the days of Lisp
(as its name suggests). Don’t confuse the following classic definition
with Java’s built-in
As you read this code, keep
a few things in mind. First,
List is an
Algebraic Data Type with structural similarities to
Option<T>. In both cases, a common
interface defines the protocol of the type, and there
are two concrete subtypes, one that represents “empty” and one that
Second, despite the similarities of structure, we’ll introduce a few more implementation idioms that get us closer to the requirements of a true algebraic data type, such ...