We are familiar with imperative data structures. In fact, there are lots of references for imperative data structures in different programming languages. In contrast, there aren't many references for declarative data structures or functional data structures. This is because functional programming 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 functional programming
- 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 functional programming 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 enumerations to implement the following functional data structures:
- Semigroup
- Monoid
- Binary Search Tree
- Linked list
- Stack
- Lazy list
Coding examples for these data structures serve as a presentation of functional programming 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.
In computer science, a Semigroup is an algebraic structure that has a set and a binary operation that takes two elements in the set and returns a Semigroup that has an associative operation.
To start, we need to have a set and a specific binary operation, or we can make this behavior generic and define a protocol as follows:
protocol Semigroup {
func operation(_ element: Self) -> Self
}
Any type that conforms to this protocol requires to implement the operation method. Here, self presents the type that is conforming to this protocol. For instance, we can extend Int to conform to the Semigroup protocol and provide a summation on itself:
extension Int: Semigroup {
func operation(_ element: Int) -> Int {
return self + element
}
}
We can test this as follows:
let number: Int = 5 number.operation(3)
This test does not ensure the associativity of the binary operations. Let's try this:
let numberA: Int = 3
let numberB: Int = 5
let numberC: Int = 7
if numberA.operation(numberB.operation(numberC)) == (numberA.operation(
numberB)).operation(numberC) {
print("Operation is associative")
}
The preceding code ensures that our binary operator is associative; therefore, our Semigroup is verified. It does not look very nice though; let's implement an operator for our operation to make it look better and more math friendly:
infix operator <> { associativity left precedence 150 }
func <> <S: Semigroup> (x: S, y: S) -> S {
return x.operation(y)
}
Let's rewrite our test with the <> operator:
if numberA <> (numberB <> numberC) == (numberA <> numberB) <> numberC {
print("Operation is associative")
}
So far, we extended only Int but we can extend any type. Let's extend arrays as an example:
extension Array: Semigroup {
func operation(_ element: Array) -> Array {
return self + element
}
}
The operation method is very similar to what we have for Int. The only difference is in the type, which is an array in this case:
print([1, 2, 3, 4] <> [5, 6, 7]) // prints "[1, 2, 3, 4, 5, 6, 7]"
Furthermore we can extend String as follows:
extension String: Semigroup {
func operation(_ element: String) -> String {
return "(self)(element)"
}
}We have established a general principle of composition (two objects combining into one) using a protocol. This pattern can be used for different purposes. For instance, we can implement a shorter version of reduce for arrays over Semigroups:
func sconcat <S: Semigroup> (initial: S, elements: [S]) -> S {
return elements.reduce(initial, combine: <>)
}
The sconcat function name stands for semigroup concat; we can test it as follows:
print(sconcat(initial: 0, elements:[1, 2, 3])) // 6 print(sconcat(initial: "", elements: ["A", "B", "C"])) // ABC print(sconcat(initial: [], elements: [[1, 2], [3, 4, 5]])) // [1, 2, 3, 4, 5]
Our last sconcat example works like flatMap and flattens elements.
Finally, our Semigroup becomes the following:
infix operator <> { associativity left precedence 150 }
func <> <S: Semigroup> (x: S, y: S) -> S {
return x.operation(y)
}
protocol Semigroup {
func operation(_ element: Self) -> Self
}
extension Int: Semigroup {
func operation(_ element: Int) -> Int {
return self + element
}
}
extension String : Semigroup {
func operation(_ element: String) -> String {
return self + element
}
}
extension Array : Semigroup {
func operation(_ element: Array) -> Array {
return self + element
}
}
func sconcat <S: Semigroup> (initial: S, elements: [S]) -> S {
return elements.reduce(initial, combine: <>)
}
A Semigroup is a great example of a simple data structure but it is not as popular as a Monoid, which we will examine in the next section.