Swift 函數式數據結構 - 鏈表

本文將使用Swift實現一個標準鏈表，在實現的過程中，遵守函數式編程的規則，無副作用，可以看到和C語言的實現還是有較大的差異。

預備知識

• enum 的各種用法
• swift的基本的模式匹配（ pattern matching )
  -- 代碼里面 case 后面部分屬于模式匹配，包含 switch case , guard case , let case 等
• extension 的用法
• guard
• generic
  遇到不懂的地方可以參閱官方文檔學習即可

鏈表定義

首先來看一下Wikipedia對List的描述

Implementation of the list data structure may provide some of the following operations :

• a constructor for creating an empty list;
• an operation for testing whether or not a list is empty;
• an operation for prepending an entity to a list
• an operation for appending an entity to a list
• an operation for determining the first component (or the "head") of a list
• an operation for referring to the list consisting of all the components of a list except for its first (this is called the "tail" of the list.)
  除了上述的要求之外，下面還將對數值型鏈表增加：判斷是否存在元素，移除指定元素，在指定元素后插入等

測試先行

基于測試先行的想法，嘗試先寫測試用例，需要注意我們的函數沒有副作用，意味著不會出現var類型變量，任何的修改都會產生新的對象。

let list0 = List<Int>()
assert(list0.isEmpty(), "list0 should be empty after constructure")

let list1 = list0.append(10)
assert(!list1.isEmpty(), "list1 should not be empty after append")
assert(list1.head == 10, "list1 should have a head valued 10")
assert(list1.tail.isEmpty(), "list1 should have an empty tail")

let list2 = [5,4,6,3,7,2].reduce(list1) {$0.append($1)}
assert(list2.head == 10, "list2 should have a head valued 10")
assert(list2.count == 7, "list2 should have 7 elements")
assert(list2.tail.count == 6, "the tail of list2 should have 6 elements")

let list3 = list2.remove(7).remove(10)
assert(list3.head == 5, "list3 should have a head valued 5")
assert(list3.count == 5, "list3 should have 5 elements")

let list4 = list3.insert(after:6, with: 11)
assert(list4.head == 5, "list4 should have a head valued 5")
assert(list4.count == 6, "list4 should have 6 elements")
assert(list4.contains(11), "list4 should contain 11")

如果按照TDD的做法我們應該先定義好類和函數體，這里根據Swift的特性選擇了ENUM來實現這個鏈表，ENUM對于模式匹配有著天然的優勢，在實現過程中，相信你也可以體會到。不過ENUM也有一些缺點，比如不能被繼承等等。看定義：

enum List<Element> {
    //表示是一個空鏈表，也表示是鏈表的結束
    case E 
    //鏈表的節點
    indirect case Node(Element,List<Element>)
    init() {
        self = .E
    }
}
extension List {
    //獲取第一個元素
    var head : Element? { 
        return nil
    }
    //獲取去掉第一個元素之后的鏈表
    var tail : List<Element> { 
        return .E
    }
    //在鏈表最后追加新元素
    func append(_ elem : Element) -> List<Element> { 
        return self
    }
    var count : Int { 
        return 0
    }
    func isEmpty() -> Bool { 
        return true
    }
}
//只有Equatable的對象才能執行按值刪除，插入和判斷是否存在
extension List where Element:Equatable {
    func remove(_ elem : Element) -> List<Element> {
        return self
    }
    func insert(after existElem : Element, with elem : Element ) -> List<Element> {
        return self
    }
    func contains(_ elem : Element) -> Bool {
        return false
    }
}

上面的定義分成了三個部分，第一個部分是構造基本定義，構造的時候會創建一個空鏈表，其中 indirect 的含義表示會嵌套使用 List ，這個修飾符也可以放在 enum 的前面，含義相同。第二部分主要定義了空鏈表判斷，元素數量，獲取頭尾，插入操作，對于 head 和 tail ，可以對應到 Node 定義上， Node 的兩個元素分別為 head 和 tail 。第三部分定義要求 Element 實現了 Equatable 的協議，只要可以判斷是否包含特定元素，刪除指定元素，以及在第一個指定元素后插入操作。

實現

好了，定義完成了，跑一下測試用例，bingo，第一條 assert 通過，第二條失敗，因為第二條要求執行 append 之后 isEmpty 失敗，所以接下來修改 append 和 isEmpty 這兩個實現，實現如下：

//在鏈表最后追加新元素
    func append(_ elem : Element) -> List<Element> {
        guard case let .Node(head, tail) = self else { return .Node(elem,.E) }
        return .Node(head, tail.append(elem))
    }
    func isEmpty() -> Bool {
        if case .E = self { return true }
        return false
    }

首先 isEmpty 的實現非常簡單，不再贅述， append 的實現使用了 guard 和模式匹配保證接下來的操作是基于 .Node(head, tail) 的，否則的話就是空鏈表，我們創建并返回只有一個元素的鏈表 .Node(elem, .E) ，到這里應該就可以跑過剛才不過的用例了；對于非空鏈表， .Node(head, tail.append(elem)) 創建了一個新的鏈表，并把新的元素插入進去。這里如果沒有看明白的話簡單解釋一下執行過程。

//假設我們有一個鏈表，其中有4個元素，分別為1，2，3，那么這個鏈表的表示應該為：
.Node(1, .Node(2, .Node(3, .E)))
//插入操作把append命令從head分別傳遞給下一個元素，幾個步驟
.Node(1, .Node(2, .Node(3, .E))).append(4) ->
.Node(1, .Node(2, .Node(3, .E)).append(4)) ->
.Node(1, .Node(2, .Node(3, .E).append(4))) ->
.Node(1, .Node(2, .Node(3, .E.append(4)))) ->
//.E.append(4) 執行結果為 .Node(4, .E)
.Node(1, .Node(2, .Node(3, .Node(4, .E))))

上面的代碼明白之后后序的代碼就不會有什么問題了，回頭來看開頭的測試用例，block在 head 和 tail 了，下面實現這兩個函數，前面也分析過了，其實 List 結構主要就是 .Node(head, tail) 。

//獲取第一個元素
    var head : Element? {
        guard case let .Node(head, _) = self else { return nil }
        return head
    }
    //獲取去掉第一個元素之后的鏈表
    var tail : List<Element> {
        guard case let .Node(_, tail) = self else { return .E }
        return tail
    }

接下來是 count 的實現

var count : Int {
        switch self {
        case .E :
            return 0
        case .Node(_, let tail):
            return tail.count + 1
        }
    }

現在跑一下測試用例會發現前面三組都通過了，第四組因為用到了 remove 還沒有實現，所以失敗了，思考一下移除一個元素的過程，很明顯需要知道如何判斷相等，所以這里要求 Element 實現了 Equatable 協議，不然編譯的時候會發現 == 無法調用。如何移除元素之后再把前面的部分和后面的部分鏈接起來呢？

假設鏈表是 .Node(1, .Node(2, .Node(3, .Node(4, .Node(5, .E))))) ，現在要移除其中一個元素，分兩種情況分析：

1. 刪除第一個元素：比較簡單，直接返回tail即可
2. 刪除其它元素，和 append 的思想是一樣的，保留 head ，然后在 tail 部分執行刪除

實現如下：

func remove(_ elem : Element) -> List<Element> {
        switch self {
        case .E :
            return .E
        case .Node(elem, let tail):
            return tail
        case let .Node(head, tail):
            return .Node(head, tail.remove(elem))
        }
    }

以及 contains 的實現：

func contains(_ elem : Element) -> Bool {
        guard case let .Node(head, tail) = self else {return false}
        return head == elem || tail.contains(elem)
    }

到這里除了 insert 的沒有實現導致最后一組用例無法通過，留下一個 insert 給大家做課后作業。

后序計劃

• Tree
• R-B Tree

 

來自：http://www.jianshu.com/p/f40e1d8c9df4