We are familiar with imperative data structures. In fact, there are lots of references to imperative data structures in different programming languages. In contrast, there aren't many references to declarative data structures or functional data structures. This is because FP languages are not as mainstream as imperative programming languages. Additionally, designing and implementing functional data structures is more difficult in comparison to imperative counterparts because of the following reasons:

• Mutability is not recommended in FP
• Functional data structures are expected to be more flexible than their imperative counterparts

Imperative data structures rely heavily on mutability and assignments and making them immutable needs extra development effort. Whenever we change an imperative data structure, we basically override the previous version; however, this is not the case with declarative programming as we expect that both the previous and new versions of the functional data structure will continue to survive and be utilized.

We might think: why bother with functional data structures as they are more difficult to design and implement? There are two answers to this question: first of all, functional data structures are efficient and immutable data structures. Secondly, they support FP paradigms. We have already seen an example of these when we were introduced to algebraic data types in Chapter 4, Enumerations and Pattern Matching.

In this chapter, we will further explore functional data structures with coding examples. The content of this chapter is heavily inspired by Purely Functional Data Structures, Chris Okasaki, Cambridge University Press, which is a great reference on this topic to date and has various examples with ML and Haskell programming languages. Reading Okasaki's book is highly recommended for functional programmers. In this chapter, we will cover the topic and explore some of the examples in Okasaki's book in Swift.

Particularly, we will utilize structs and enums to implement the following functional data structures:

• Semigroups
• Monoids
• Binary Search Trees
• Linked lists
• Stacks
• Lazy lists

Coding examples for these data structures serve as a presentation of FP paradigms and techniques and they are not going to be complete.

We know that immutability is the most important property of functional data structures. To design and implement immutable data structures, we will not change a functional data structure and instead create a new version that lives along with the previous version. In fact, we will copy the parts that need to be changed without touching the original version of the data structure. So we will use value types such as structs and enumerations to be able to achieve this. In addition, as we will not change the original data structure directly, we will be able to share the original data structure parts with the new structure without being worried about how changing one version would affect the other version. Let's examine how we will achieve this by implementing different functional data structures.