Swift 函数式数据结构 - 链表

   <p>本文将使用Swift实现一个标准链表，在实现的过程中，遵守函数式编程的规则，无副作用，可以看到和C语言的实现还是有较大的差异。</p>    <h2><strong>预备知识</strong></h2>    <ul>     <li>enum 的各种用法</li>     <li>swift的基本的模式匹配（ pattern matching )<br> -- 代码里面 case 后面部分属于模式匹配，包含 switch case , guard case , let case 等</li>     <li>extension 的用法</li>     <li>guard</li>     <li>generic<br> 遇到不懂的地方可以参阅官方文档学习即可</li>    </ul>    <h2><strong>链表定义</strong></h2>    <p>首先来看一下Wikipedia对List的描述</p>    <p>Implementation of the list data structure may provide some of the following operations :</p>    <ul>     <li>a constructor for creating an empty list;</li>     <li>an operation for testing whether or not a list is empty;</li>     <li>an operation for prepending an entity to a list</li>     <li>an operation for appending an entity to a list</li>     <li>an operation for determining the first component (or the "head") of a list</li>     <li>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.)<br> 除了上述的要求之外，下面还将对数值型链表增加：判断是否存在元素，移除指定元素，在指定元素后插入等</li>    </ul>    <h2><strong>测试先行</strong></h2>    <p>基于测试先行的想法，尝试先写测试用例，需要注意我们的函数没有副作用，意味着不会出现var类型变量，任何的修改都会产生新的对象。</p>    <pre>  <code class="language-swift">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")</code></pre>    <p>如果按照TDD的做法我们应该先定义好类和函数体，这里根据Swift的特性选择了ENUM来实现这个链表，ENUM对于模式匹配有着天然的优势，在实现过程中，相信你也可以体会到。不过ENUM也有一些缺点，比如不能被继承等等。看定义：</p>    <pre>  <code class="language-swift">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      }  }</code></pre>    <p>上面的定义分成了三个部分，第一个部分是构造基本定义，构造的时候会创建一个空链表，其中 indirect 的含义表示会嵌套使用 List ，这个修饰符也可以放在 enum 的前面，含义相同。第二部分主要定义了空链表判断，元素数量，获取头尾，插入操作，对于 head 和 tail ，可以对应到 Node 定义上， Node 的两个元素分别为 head 和 tail 。第三部分定义要求 Element 实现了 Equatable 的协议，只要可以判断是否包含特定元素，删除指定元素，以及在第一个指定元素后插入操作。</p>    <h2><strong>实现</strong></h2>    <p>好了，定义完成了，跑一下测试用例，bingo，第一条 assert 通过，第二条失败，因为第二条要求执行 append 之后 isEmpty 失败，所以接下来修改 append 和 isEmpty 这两个实现，实现如下：</p>    <pre>  <code class="language-swift">//在链表最后追加新元素      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      }</code></pre>    <p>首先 isEmpty 的实现非常简单，不再赘述， append 的实现使用了 guard 和模式匹配保证接下来的操作是基于 .Node(head, tail) 的，否则的话就是空链表，我们创建并返回只有一个元素的链表 .Node(elem, .E) ，到这里应该就可以跑过刚才不过的用例了；对于非空链表， .Node(head, tail.append(elem)) 创建了一个新的链表，并把新的元素插入进去。这里如果没有看明白的话简单解释一下执行过程。</p>    <pre>  <code class="language-swift">//假设我们有一个链表，其中有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))))</code></pre>    <p>上面的代码明白之后后序的代码就不会有什么问题了，回头来看开头的测试用例，block在 head 和 tail 了，下面实现这两个函数，前面也分析过了，其实 List 结构主要就是 .Node(head, tail) 。</p>    <pre>  <code class="language-swift">//获取第一个元素      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      }</code></pre>    <p>接下来是 count 的实现</p>    <pre>  <code class="language-swift">var count : Int {          switch self {          case .E :              return 0          case .Node(_, let tail):              return tail.count + 1          }      }</code></pre>    <p>现在跑一下测试用例会发现前面三组都通过了，第四组因为用到了 remove 还没有实现，所以失败了，思考一下移除一个元素的过程，很明显需要知道如何判断相等，所以这里要求 Element 实现了 Equatable 协议，不然编译的时候会发现 == 无法调用。如何移除元素之后再把前面的部分和后面的部分链接起来呢？</p>    <p>假设链表是 .Node(1, .Node(2, .Node(3, .Node(4, .Node(5, .E))))) ，现在要移除其中一个元素，分两种情况分析：</p>    <ol>     <li>删除第一个元素：比较简单，直接返回tail即可</li>     <li>删除其它元素，和 append 的思想是一样的，保留 head ，然后在 tail 部分执行删除</li>    </ol>    <p>实现如下：</p>    <pre>  <code class="language-swift">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))          }      }</code></pre>    <p>以及 contains 的实现：</p>    <pre>  <code class="language-swift">func contains(_ elem : Element) -> Bool {          guard case let .Node(head, tail) = self else {return false}          return head == elem || tail.contains(elem)      }</code></pre>    <p>到这里除了 insert 的没有实现导致最后一组用例无法通过，留下一个 insert 给大家做课后作业。</p>    <h2><strong>后序计划</strong></h2>    <ul>     <li>Tree</li>     <li>R-B Tree</li>    </ul>    <p> </p>    <p>来自：http://www.jianshu.com/p/f40e1d8c9df4</p>    <p> </p>