Functional Programming for Java Developers

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.

Lists

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 List type.

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 represents “non-empty.”

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 ...