Functional and Concurrent Programming: Core Concepts and Features

Chapter 7

Recursion on Lists

Because functional lists are a recursive data structure—the tail of a non-empty list is a list—many list-processing functions nicely fit a recursive pattern in which recursion is applied to the tail of a list. This chapter uses this pattern to (re)implement several common list functions. The objective is twofold: It is both an exposure to standard list functions and a way to practice recursive thinking. Other patterns are also explored, in which recursion is applied to sublists other than the tail. Some performance considerations are discussed, such as the use of tail recursion or pure functions that rely internally on mutable structures.

Note

The Scala collection library implements many list operations as methods ...