Learning Functional Programming

Chapter 4. Functional Data Structures

Data structures are a foundational concept in computer science. Along with algorithms, they are a staple of what a computer science student or programmer must master. As with the phrase functional pattern, functional data structure is not an established concept with a consistent definition in the canon of code.

In this book, I will refer to two things as functional data structures.

• Structures used in functional patterns, such as Option, Either, Try, List. These are monads.

• Ordinary data structures that are implemented in a functional way so that they don’t mutate state, such as a linked list.

In this chapter, we will treat the first kind of functional data structures and then briefly cover some of the ideas surrounding ordinary data structures implemented in a functional way. Before we look at particular data structures, let me mention an idea about functional data structures that has been discussed in the literature. First, there is this quote from Alan Perlis:

It is better to have 100 functions operate on one data structure than to have 10 functions operate on 10 data structures.

Seasoned functional programmers tend to use a small set of data structures: linked lists, arrays, and hash tables, as well as structures such as Option, Either, and Try, to name a few. We will examine these next. I believe the idea behind this quote is that fewer data structures results in more uniformity and simplicity in the codebase. Now, let’s look at ...