Our LinkedList needs a method to create it as empty:

static func empty() -> LinkedList {
    return .end
}

This is as simple as returning .end.

We need to have a way to append items to LinkedList, so we implement it as follows:

func cons(_ element: Element) -> LinkedList {
    return .node(data: element, next: self)
}

This simple method appends the data to the front of LinkedList; in other words, it is like a push operation to a stack. We can test it as follows:

let functionalLinkedList = LinkedList<Int>.end.cons(1).cons(2).cons(3)
print(functionalLinkedList)

The result of this operation should be the following:

node(3, LinkedList<Swift.Int>.node(2, LinkedList<Swift.Int>.node(
  1, LinkedList<Swift.Int>.end)))

Functional programming languages such as Haskell and Scala have operators for cons. It is : in Haskell and :: in Scala. As we cannot use : in Swift to define an infix operator, we are going to use <| instead:

infix operator <| { associativity right precedence 100 }

func <| <T>(lhs: T, rhs: LinkedList<T>) -> LinkedList<T> {
    return .node(data: lhs, next: rhs)
}

We will be able to test it as follows:

let functionalLLWithCons = 3 <| 2 <| 1 <| .end

This statement produces the exact same result.

Again, this LinkedList is far from complete but we already achieved great reusability as it is functional. We can use/share our functionalLinkedList with other linked lists without worrying about changes and inconsistencies. Let's examine the following:

let secondLL = functionalLinkedList.cons(4)
let thirdLL = functionalLinkedList.cons(5)
let fourthLL = LinkedList<Int>.node(data: 1, next: secondLL)

In the preceding examples, we use functionalLinkedList and add a new item (4) to it to obtain secondLL and 5 to obtain thirdLL. Also, we use secondLL to create fourthLL.

To make this LinkedList a little more interesting, we will develop a contains method similar to the one that we developed for the BST:

static func contains(_ key: Element, list: LinkedList<Element>) -> Bool {
    switch list {
    case .end:
        return false
    case .node(let data, let next):
        if key == data {
            return true
        } else {
            return contains(key, list: next)
        }
    }
}

This method recursively checks for a specific element in LinkedList and returns true if it finds the element:

print(LinkedList.contains(1, list: functionalLinkedList))

The result of this expression is going to be true.

We can implement a computed size property to calculate the size of linked list as follows:

var size: Int {
    switch self {
    case .node(_, let next):
        return 1 + next.size
    case .end:
        return 0
    }
}

This method recursively goes through LinkedList and counts the number of nodes:

print(functionalLinkedList.size)

The result is going to be 3 in this example.

We can implement a computed property to provide an array of elements as follows:

var elements: [Element] {
    switch self {
    case .node(let data, let next):
        return [data] + next.elements
    case .end:
        return []
    }
}

Here, we recur through LinkedList and return an array of data. We will be able to use this property as follows:

print(functionalLinkedList.elements)

This statement prints [3, 2, 1].

Another common operation that LinkedList requires is a way to check whether it is empty. We can easily implement it in the following way:

var isEmpty: Bool {
    switch self {
    case .node(_ , _):
        return false
    case .end:
        return true
    }
}

To test this computed property, we will create an empty LinkedList as follows:

let emptyLL = LinkedList<Int>.end
print(emptyLL.isEmpty)

print(functionalLinkedList.isEmpty)

In the preceding example, the first print statement results in true and the second results in false.

You may have wondered if we are going to be able to apply higher-order functions such as map, filter, and reduce to our linked list. We have implemented our linked list with a recursive enum and the recursive pattern is well-suited to higher-order functions.

Let's start with map:

func map<T>(_ transform: (Element) -> T) -> LinkedList<T> {
    switch self {
    case .end:
        return .end
    case .node(let data, let next):
        return transform(data) <| next.map(transform)
    }
}

Using this method, we will be able to transform elements in our linked list. Nothing fancy here; we use the same cons operator that we defined before. The following statement will test our method:

let mappedFunctionalLL = functionalLinkedList.map { $0 * 2 }

The result should be the following:

node(6, LinkedList<Swift.Int>.node(4, LinkedList<Swift.Int>.node(
  2, LinkedList<Swift.Int>.end)))

So we can easily multiply elements in our linked list by 2.

Let's continue with the filter method:

func filter(_ predicate: ((Element) -> Bool)) -> LinkedList<Element> {
    switch self {
    case .end:
        return .end
    case .node(let data, let next):
        return predicate(data) ? data <| next.filter(predicate) :
          next.filter(predicate)
    }
}

Here, we check whether the predicate yields a result first. If it does, then we apply our cons operator to the data and recursively filter the next element. Otherwise, we just recursively apply filter to the next element. We can test this method as follows:

let filteredFunctionalLL = functionalLinkedList.filter { $0 % 2 == 0 }

In the preceding code example, we filter our linked list to the ones that are even. This statement results in the following:

node(2, LinkedList<Swift.Int>.end)

It is great to be able to map and filter our linked list, but we need to have a reduce method as well. Let's implement this:

func reduce<Value>(_ initial: Value, combine: (Value, Element) -> Value)
  -> Value {
    switch self {
    case .end:
        return initial
    case .node(let data, let next):
        return next.reduce(combine(initial, data), combine: combine)
    }
}

In the preceding code example, we go through the linked list's elements recursively and reduce the values to a single value. The following code presents a usage example:

let reducedFunctionalLL = functionalLinkedList.reduce(0) { $0 + $1}

The result of this expression is going to be 6.

At the end, our LinkedList becomes the following:

/// Operator
infix operator <| { associativity right precedence 100 }

func <| <T>(lhs: T, rhs: LinkedList<T>) -> LinkedList<T> {
    return .node(data: lhs, next: rhs)
}

/// LinkedList

enum LinkedList<Element: Equatable> {
    case end
    indirect case node(data: Element, next: LinkedList<Element>)

    var size: Int {
        switch self {
        case .node(_, let next):
            return 1 + next.size
        case .end:
            return 0
        }
    }

    var elements: [Element] {
        switch self {
        case .node(let data, let next):
            return [data] + next.elements
        case .end:
            return []
        }
    }

    var isEmpty: Bool {
        switch self {
        case .node(_ , _):
            return false
        case .end:
            return true
        }
    }

    static func empty() -> LinkedList {
        return .end
    }

    func cons(_ element: Element) -> LinkedList {
        return .node(data: element, next: self)
    }
 
    func map<T>(_ transform: (Element) -> T) -> LinkedList<T> {
        switch self {
        case .end:
            return .end
        case .node(let data, let next):
            return transform(data) <| next.map(transform)
        }
    }
 
    func filter(_ predicate: ((Element) -> Bool)) -> LinkedList<Element> {
        switch self {
        case .end:
            return .end
        case .node(let data, let next):
            return predicate(data) ? data <| next.filter(predicate)
              : next.filter(predicate)
        }
    }
 
    func reduce<Value>(_ initial: Value, combine: (Value, Element)
      -> Value) -> Value {
        switch self {
        case .end:
            return initial
        case .node(let data, let next):
            return next.reduce(combine(initial, data), combine: combine)
        }
    }
 
    static func contains(_ key: Element, list: LinkedList<Element>)
      -> Bool {
        switch list {
        case .end:
            return false
        case .node(let data, let next):
            if key == data {
                return true
            } else {
                return contains(key, list: next)
            }
        }
    }
}