Swift 函数式数据结构 - 链表

vr112058 3年前
   <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>