前情提要 "Scala函數式編程指南（一）函數式思想介紹" "scala函數式編程（二） scala基礎語法介紹" "Scala函數式編程（三） scala集合和函數" "Scala函數式編程（四）函數式的數據結構上" 1.List代碼解析今天介紹的內容，主要是對上一篇介紹的scala函數式數 ...

前情提要

1.List代碼解析

今天介紹的內容，主要是對上一篇介紹的scala函數式數據結構補充，主要講代碼。可以先看看上一節，主要講的是函數式的list，Scala函數式編程（四）函數式的數據結構上。這些代碼我都放在我的公眾號裡面，包括函數式的List以及一個函數式的二叉搜索樹，關註公眾號：哈爾的數據城堡，回覆“scala樹數據結構”就能直接獲得（寫文章不容易，大哥大姐關註下吧 :) ）。

話說回來，上一篇中，主要介紹了List的一些基礎用法，包括定義基礎的結構，節點Cons和結尾的Nil。以及使用一個object List來定義基礎的List操作。

//定義List為特質，Nil和Cons為結尾和中間的Node
sealed trait List[+A]

case object Nil extends List[Nothing]

case class Cons[+A](head: A, tail: List[A]) extends List[A] {
  override def toString: String = s"$head :: ${tail.toString}"
}


//Listc操作的定義方法，object相當於java中的靜態類，裡面的方法可以直接調用
object List {

  def sum(ints: List[Int]): Int = ints match {
    case Nil => 0
    case Cons(x,xs) => x + sum(xs)
  }

  def map[A,B](l: List[A],f: A => B): List[B] =l match {
    case Nil              => Nil
    case Cons(head, tail) =>Cons(f(head), map(tail,f))
  }
  def apply[A](a: A*): List[A] =
    if (a.isEmpty) Nil
    else Cons(a.head, apply(a.tail: _*))

  def empty[A]: List[A] = Nil


  object ops {
    //定義隱式轉換，這個是為了擴充List的操作而準備的，可以看看最下麵是如果使用的
    implicit def listOps[A](list: List[A]): ListOps[A] = new ListOps(list)
  }
}

關於節點Cons和Nil的定義和上一節一樣，只是Cons多了個重寫的toString方法。

簡單再說下，這裡呢，在object List裡面，在裡面我們定義了apply方法，可以初始化生成一個List。以及上一節提到的sum和map方法。如果對這些看不明白可以看看上一節的內容。

但這樣的話當我們要調用sum方法的時候，只能通過object List來調用，類似下麵這樣：

//使用object List裡面的apply方法初始化，生成List
scala> val numList = List(1,2,3,4)
numList: List[Int] = 1 :: 2 :: 3 :: 4 :: Nil

//使用object List裡面的sum方法
scala> List.sum(numList)
res0: Int = 10

但是呢，我們日常使用的時候可不是這樣呀，我們更熟悉的應該是要這樣：

//使用object List裡面的apply方法初始化，生成List
scala> val numList = List(1,2,3,4)
numList: List[Int] = 1 :: 2 :: 3 :: 4 :: Nil

//直接使用numList內置的方法來處理
scala> numList.sum()
res0: Int = 10

更加通用的做法，應該是通過List本身，來調用方法，就像上面看到的那樣。通常的做法，是直接加在Cons裡面，但由於Cons是繼承自trait List[+A]，所以大家（包括）Nil裡面都需要定義那一堆方法了，有沒有別的辦法呢？

有的，scala的又一個語法糖，隱式轉換，就是上面object List裡面的ops。

  object ops {
    //定義隱式轉換，這個是為了擴充List的操作而準備的，可以看看最下麵是如果使用的
    implicit def listOps[A](list: List[A]): ListOps[A] = new ListOps(list)
  }

隱式轉換主要是通過implicit這個關鍵字定義的，當然隱式轉換還有其他用法，不管這裡的用法算是最常見的用法了。

隱式轉換函數，看的主要是參數，以及返回，函數名字（這裡名字是listOps）是不重要的，起什麼都沒關係。

隱式轉換的作用這裡不多解釋，可以百度看看，簡單說就是在需要的時候，將一個類型轉換成另一種類型。這裡的作用，是在特定的情況下將我們定義的List轉成ListOps類型，而ListOps類，則在下麵給出。

//擴充List的操作
private[list] final class ListOps[A](list: List[A]) {
//導入隱式轉換函數，因為下麵的處理也是需要隱式轉換
  import List.ops._

  //使用遞歸實現，foldRight的實現就是調用了這個函數，這麼做是為了復用
  //代碼復用是函數式中很重要的一個特性，看下麵append方法就可以明白
  def foldRightAsPrimary[B](z: B)(f: (A, B) => B): B = list match {
    case Nil              => z
    case Cons(head, tail) => f(head, tail.foldRightAsPrimary(z)(f))
  }

  def foldRight[B](z: B)(f: (A, B) => B): B = foldRightViaFoldLeft(z)(f)

  def map[B](f: A=> B): List[B] = list match {
    case Nil              => Nil
    case Cons(head, tail) => Cons(f(head), tail.map(f))
  }

}

有了這段代碼後，當我們需要使用map的時候，就可以不用再藉助object List代勞，而可以直接使用，就像這樣：

//使用object List裡面的apply方法初始化，生成List
scala> val numList = List(1,2,3,4)
numList: List[Int] = 1 :: 2 :: 3 :: 4 :: Nil

//直接使用numList內置的方法來處理，而不是List.map(numList,function)
scala> numList.map(function)

當代碼檢測到List調用map方法，但List內部並沒有map方法，就會觸發隱式轉換，轉換成ListOps類型，調用ListOps類型裡面的map方法，然後返回一個List作為結果。雖然經過了諸多波折，但調用者是感受不到的，反而感覺就像是List裡面本身的map方法一樣。在Spark裡面就有很多這樣的操作。

如上面的代碼，現在我們可以直接使用numList.map(function)這樣的方式，就像List裡面本身就有map函數一樣來使用了。

2.二叉搜索樹

在上一篇末尾，給出了一份還未完成的數據結構，二叉搜索樹當作練習。這一節就來講講這個。

其實如果把之前的List都看懂的話，其實二叉搜索樹並沒有什麼難點。

二叉搜索樹，是樹，自然就有葉節點和葉子節點（就是末尾）。不過這次和List不一樣的是，沒有使用隱式轉換，所以我們定義的就不是特質了，而是先定義一個抽象類。然後讓葉節點和葉子節點繼承它。

  //定義一個二叉樹的抽象類
  sealed abstract class TreeMap[+A] extends AbstractMap[Int, A] {

    def add[B >: A](kv: (Int, B)): TreeMap[B] = ???
    def deleteMin: ((Int, A), TreeMap[A]) = ???
    def delete(key: Int): TreeMap[A] = ???
    def get(key: Int): Option[A] = ???
    def +[A1 >: A](kv: (Int, A1)): TreeMap[A1] =  ???
    def -(k: Int): TreeMap[A] = ???
    override def toList: List[(Int, A)] = ???
    def iterator: Iterator[(Int, A)] =???
  }
  
  //葉子節點，也就是每個分支的末尾，繼承了上面的抽象類
  case class Leaf() extends TreeMap[Nothing]
  //葉節點，包含左右和內容，繼承了上面的抽象類
  case class Node[+A](key: Int, value: A,
                      left: TreeMap[A], right: TreeMap[A]) extends TreeMap[A]

二叉樹中有有基礎的增刪查操作，還重載了兩個符號，+和-分別代表增加和刪除。對了，這裡的???，其實和python裡面的pass是一樣的，就充當個占位符，告訴編譯器這裡會有東西的，先別報錯。

然後主要就是要實現二叉樹裡面空缺的代碼，其實熟悉樹結構的同學應該都知道，遞歸是樹天生的基因。所以這裡自然都是要通過遞歸實現的。不過在編寫前，還是要提一下，一般函數式編程裡面，不會使用可變變數（var），也不會使用可變的數據結構（ListBuff）。

實現過程也沒什麼好解釋的，其實就是通過遞歸，以及scala的模式匹配，如果碰到葉子節點就掛掉，不是就遞歸去進行。直接看代碼。這裡主要介紹add方法，其他的基本都是類似的：


  sealed abstract class TreeMap[+A] extends AbstractMap[Int, A] {
    ......
    //使用模式匹配，實現遞歸操作，主要是找到對應的位置，插入數據
    def add[B >: A](kv: (Int, B)): TreeMap[B] = {

      val (key, value) = kv
      //this就是當前的類型，可能是葉節點，也可能是葉子節點
      this match {
        case Node(nodeKey, nodeValue, left, right) => {
          //按照二叉搜索樹的規則，進行遞歸
          if(nodeKey > key)
            Node(nodeKey, nodeValue, left.add((key,value)), right)
          else if(nodeKey < key)
            Node(nodeKey, nodeValue, left, right.add((key,value)))
          else
            Node(nodeKey, value, left, right)
        }
        //如果是葉子節點，則新生成一個葉節點，返回
        case Leaf() => {
          Node(key, value, Leaf(), Leaf())
        }
      }

      ......
    }

根據二叉搜索樹的規則，新鍵大於節點的鍵的時候，插入右邊，小於節點的鍵的時候，插入到左邊。然後約定好結束條件，也就是碰到葉子節點的時候返回。這樣一來就完成了插入的操作。後面無論是刪除，還是查找，都是同樣的思路。

而重載運算符方法，比如重載+方法，就是直接調用上面的add方法，即直接復用。然後看看object TreeMap。

  object TreeMap {

    def empty[A]: TreeMap[A] = Leaf()

    def apply[A](kvs: (Int, A)*): TreeMap[A] = {
      kvs.toSeq.foldLeft(empty[A])(_ + _)
    }
  }

這個object主要作用有兩個，一個是生成葉子節點，一個是初始化一棵樹（註意是apply方法）。和List一樣，這裡也是用多參數的輸入方式，不同的是這裡沒有用遞歸，而是直接把多個參數轉化成一個序列，然後用foldLeft，逐個累加。從而實現初始化樹。

OK，到這裡就結束了，最後還是希望你能夠自己試著寫下tree的代碼，寫完再用test case測試下，編程功底就是這樣一步一步打下的。

3.小結

函數式的數據結構篇到此就結束，希望在這裡，你能明白函數式的數據結構與我們最開始接觸到的數據結構的實現有哪些不同，又為何要大費周章用函數式的方式實現！！

很多scala的教程介紹到這裡就一句話，scala的預設數據結構是不可變的，如果可變的要怎樣巴拉巴拉，這樣容易讓人陷入知其然不知其所以然的地步。

同時我也一直決定，學習語言的話，語法知識最表層的東西。真正深入學習一門語言，你需要逐漸知道這門語言在設計上的取捨，甚至是設計上的哲學，比如python的至簡哲學。

而在深入這些東西的過程中，語法自然而然就掌握了，比如較為晦澀的隱式轉換。在這裡就會知道隱式轉換是這樣用的，原來spark裡面一直都有這個東西參與！！！

接下來一篇將介紹scala中的錯誤處理方式，依舊是函數式的處理方式，像java中的try{}catch{}肯定是非函數式的，那麼scala是怎麼實現的呢，下一篇就來介紹:)

如果有什麼疑問，也歡迎留言。

以上~

Scala函數式編程（四）函數式的數據結構 下

1.List代碼解析

2.二叉搜索樹

3.小結

Scala函數式編程（四）函數式的數據結構下