前情提要
Scala函數(shù)式編程指南（一） 函數(shù)式思想介紹
scala函數(shù)式編程（二） scala基礎(chǔ)語法介紹
Scala函數(shù)式編程（三） scala集合和函數(shù)
Scala函數(shù)式編程（四）函數(shù)式的數(shù)據(jù)結(jié)構(gòu) 上
1.List代碼解析
今天介紹的內(nèi)容约巷，主要是對上一篇介紹的scala函數(shù)式數(shù)據(jù)結(jié)構(gòu)補充雏门，主要講代碼〕喊觯可以先看看上一節(jié)，主要講的是函數(shù)式的list派撕，Scala函數(shù)式編程（四）函數(shù)式的數(shù)據(jù)結(jié)構(gòu) 上删咱。這些代碼我都放在我的公眾號里面，包括函數(shù)式的List以及一個函數(shù)式的二叉搜索樹肆汹，關(guān)注公眾號：哈爾的數(shù)據(jù)城堡，回復(fù)“scala樹數(shù)據(jù)結(jié)構(gòu)”就能直接獲得（寫文章不容易予权，大哥大姐關(guān)注下吧 :) ）昂勉。
話說回來，上一篇中伟件，主要介紹了List的一些基礎(chǔ)用法硼啤，包括定義基礎(chǔ)的結(jié)構(gòu)，節(jié)點Cons和結(jié)尾的Nil。以及使用一個object List來定義基礎(chǔ)的List操作谴返。
//定義List為特質(zhì)煞肾，Nil和Cons為結(jié)尾和中間的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相當(dāng)于java中的靜態(tài)類嗓袱，里面的方法可以直接調(diào)用
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 {
//定義隱式轉(zhuǎn)換籍救，這個是為了擴充List的操作而準(zhǔn)備的，可以看看最下面是如果使用的
implicit def listOps[A](list: List[A]): ListOps[A] = new ListOps(list)
}
}
關(guān)于節(jié)點Cons和Nil的定義和上一節(jié)一樣渠抹，只是Cons多了個重寫的toString方法蝙昙。
簡單再說下，這里呢梧却，在object List里面奇颠，在里面我們定義了apply方法，可以初始化生成一個List放航。以及上一節(jié)提到的sum和map方法烈拒。如果對這些看不明白可以看看上一節(jié)的內(nèi)容。
但這樣的話當(dāng)我們要調(diào)用sum方法的時候广鳍，只能通過object List來調(diào)用荆几，類似下面這樣：
//使用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
但是呢赊时，我們?nèi)粘Ｊ褂玫臅r候可不是這樣呀吨铸，我們更熟悉的應(yīng)該是要這樣：
//使用object List里面的apply方法初始化，生成List
scala> val numList = List(1,2,3,4)
numList: List[Int] = 1 :: 2 :: 3 :: 4 :: Nil
//直接使用numList內(nèi)置的方法來處理
scala> numList.sum()
res0: Int = 10
更加通用的做法祖秒，應(yīng)該是通過List本身诞吱，來調(diào)用方法，就像上面看到的那樣狈涮。通常的做法狐胎，是直接加在Cons里面鸭栖，但由于Cons是繼承自trait List[+A]歌馍，所以大家（包括）Nil里面都需要定義那一堆方法了，有沒有別的辦法呢晕鹊？
有的松却，scala的又一個語法糖，隱式轉(zhuǎn)換溅话，就是上面object List里面的ops晓锻。
object ops {
//定義隱式轉(zhuǎn)換，這個是為了擴充List的操作而準(zhǔn)備的飞几，可以看看最下面是如果使用的
implicit def listOps[A](list: List[A]): ListOps[A] = new ListOps(list)
}
隱式轉(zhuǎn)換主要是通過implicit這個關(guān)鍵字定義的砚哆，當(dāng)然隱式轉(zhuǎn)換還有其他用法，不管這里的用法算是最常見的用法了屑墨。
隱式轉(zhuǎn)換函數(shù)躁锁，看的主要是參數(shù)纷铣，以及返回，函數(shù)名字（這里名字是listOps）是不重要的战转，起什么都沒關(guān)系搜立。
隱式轉(zhuǎn)換的作用這里不多解釋，可以百度看看槐秧，簡單說就是在需要的時候啄踊，將一個類型轉(zhuǎn)換成另一種類型。這里的作用刁标，是在特定的情況下將我們定義的List轉(zhuǎn)成ListOps類型颠通，而ListOps類，則在下面給出膀懈。
//擴充List的操作
private[list] final class ListOps[A](list: List[A]) {
//導(dǎo)入隱式轉(zhuǎn)換函數(shù)蒜哀，因為下面的處理也是需要隱式轉(zhuǎn)換
import List.ops._
//使用遞歸實現(xiàn)，foldRight的實現(xiàn)就是調(diào)用了這個函數(shù)吏砂，這么做是為了復(fù)用
//代碼復(fù)用是函數(shù)式中很重要的一個特性撵儿，看下面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))
}
}
有了這段代碼后，當(dāng)我們需要使用map的時候狐血，就可以不用再借助object List代勞淀歇，而可以直接使用，就像這樣：
//使用object List里面的apply方法初始化匈织，生成List
scala> val numList = List(1,2,3,4)
numList: List[Int] = 1 :: 2 :: 3 :: 4 :: Nil
//直接使用numList內(nèi)置的方法來處理浪默，而不是List.map(numList,function)
scala> numList.map(function)
當(dāng)代碼檢測到List調(diào)用map方法，但List內(nèi)部并沒有map方法缀匕，就會觸發(fā)隱式轉(zhuǎn)換纳决，轉(zhuǎn)換成ListOps類型，調(diào)用ListOps類型里面的map方法乡小，然后返回一個List作為結(jié)果阔加。雖然經(jīng)過了諸多波折，但調(diào)用者是感受不到的满钟，反而感覺就像是List里面本身的map方法一樣胜榔。在Spark里面就有很多這樣的操作。
如上面的代碼湃番，現(xiàn)在我們可以直接使用numList.map(function)這樣的方式夭织，就像List里面本身就有map函數(shù)一樣來使用了。
2.二叉搜索樹
在上一篇末尾吠撮，給出了一份還未完成的數(shù)據(jù)結(jié)構(gòu)尊惰，二叉搜索樹當(dāng)作練習(xí)。這一節(jié)就來講講這個。
其實如果把之前的List都看懂的話弄屡，其實二叉搜索樹并沒有什么難點戴卜。
二叉搜索樹，是樹琢岩，自然就有葉節(jié)點和葉子節(jié)點（就是末尾）投剥。不過這次和List不一樣的是，沒有使用隱式轉(zhuǎn)換担孔，所以我們定義的就不是特質(zhì)了江锨，而是先定義一個抽象類。然后讓葉節(jié)點和葉子節(jié)點繼承它糕篇。
//定義一個二叉樹的抽象類
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)] =???
}
//葉子節(jié)點啄育，也就是每個分支的末尾，繼承了上面的抽象類
case class Leaf() extends TreeMap[Nothing]
//葉節(jié)點拌消，包含左右和內(nèi)容挑豌，繼承了上面的抽象類
case class Node[+A](key: Int, value: A,
left: TreeMap[A], right: TreeMap[A]) extends TreeMap[A]
二叉樹中有有基礎(chǔ)的增刪查操作，還重載了兩個符號墩崩，+和-分別代表增加和刪除氓英。對了，這里的???鹦筹，其實和python里面的pass是一樣的铝阐，就充當(dāng)個占位符，告訴編譯器這里會有東西的铐拐，先別報錯徘键。
然后主要就是要實現(xiàn)二叉樹里面空缺的代碼，其實熟悉樹結(jié)構(gòu)的同學(xué)應(yīng)該都知道遍蟋，遞歸是樹天生的基因吹害。所以這里自然都是要通過遞歸實現(xiàn)的。不過在編寫前虚青，還是要提一下它呀，一般函數(shù)式編程里面，不會使用可變變量（var）挟憔，也不會使用可變的數(shù)據(jù)結(jié)構(gòu)（ListBuff）钟些。
實現(xiàn)過程也沒什么好解釋的，其實就是通過遞歸绊谭，以及scala的模式匹配，如果碰到葉子節(jié)點就掛掉汪拥，不是就遞歸去進行达传。直接看代碼。這里主要介紹add方法，其他的基本都是類似的：
sealed abstract class TreeMap[+A] extends AbstractMap[Int, A] {
......
//使用模式匹配宪赶，實現(xiàn)遞歸操作宗弯，主要是找到對應(yīng)的位置，插入數(shù)據(jù)
def add[B >: A](kv: (Int, B)): TreeMap[B] = {
val (key, value) = kv
//this就是當(dāng)前的類型搂妻，可能是葉節(jié)點蒙保，也可能是葉子節(jié)點
this match {
case Node(nodeKey, nodeValue, left, right) => {
//按照二叉搜索樹的規(guī)則，進行遞歸
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)
}
//如果是葉子節(jié)點欲主，則新生成一個葉節(jié)點邓厕，返回
case Leaf() => {
Node(key, value, Leaf(), Leaf())
}
}
......
}
根據(jù)二叉搜索樹的規(guī)則，新鍵大于節(jié)點的鍵的時候扁瓢，插入右邊详恼，小于節(jié)點的鍵的時候，插入到左邊引几。然后約定好結(jié)束條件昧互，也就是碰到葉子節(jié)點的時候返回。這樣一來就完成了插入的操作伟桅。后面無論是刪除敞掘，還是查找，都是同樣的思路楣铁。
而重載運算符方法渐逃，比如重載+方法，就是直接調(diào)用上面的add方法民褂，即直接復(fù)用茄菊。然后看看object TreeMap。
object TreeMap {
def empty[A]: TreeMap[A] = Leaf()
def apply[A](kvs: (Int, A)*): TreeMap[A] = {
kvs.toSeq.foldLeft(empty[A])(_ + _)
}
}
這個object主要作用有兩個赊堪，一個是生成葉子節(jié)點面殖，一個是初始化一棵樹（注意是apply方法）。和List一樣哭廉，這里也是用多參數(shù)的輸入方式脊僚，不同的是這里沒有用遞歸，而是直接把多個參數(shù)轉(zhuǎn)化成一個序列遵绰，然后用foldLeft辽幌，逐個累加。從而實現(xiàn)初始化樹椿访。
OK乌企，到這里就結(jié)束了，最后還是希望你能夠自己試著寫下tree的代碼成玫，寫完再用test case測試下加酵，編程功底就是這樣一步一步打下的拳喻。
3.小結(jié)
函數(shù)式的數(shù)據(jù)結(jié)構(gòu)篇到此就結(jié)束，希望在這里猪腕，你能明白函數(shù)式的數(shù)據(jù)結(jié)構(gòu)與我們最開始接觸到的數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)有哪些不同冗澈，又為何要大費周章用函數(shù)式的方式實現(xiàn)！陋葡！
很多scala的教程介紹到這里就一句話亚亲，scala的默認(rèn)數(shù)據(jù)結(jié)構(gòu)是不可變的，如果可變的要怎樣巴拉巴拉腐缤，這樣容易讓人陷入知其然不知其所以然的地步捌归。
同時我也一直決定，學(xué)習(xí)語言的話柴梆，語法知識最表層的東西陨溅。真正深入學(xué)習(xí)一門語言，你需要逐漸知道這門語言在設(shè)計上的取舍绍在，甚至是設(shè)計上的哲學(xué)门扇，比如python的至簡哲學(xué)。
而在深入這些東西的過程中偿渡，語法自然而然就掌握了臼寄，比如較為晦澀的隱式轉(zhuǎn)換。在這里就會知道隱式轉(zhuǎn)換是這樣用的溜宽，原來spark里面一直都有這個東西參與＜！适揉！
接下來一篇將介紹scala中的錯誤處理方式留攒，依舊是函數(shù)式的處理方式，像java中的try{}catch{}肯定是非函數(shù)式的嫉嘀，那么scala是怎么實現(xiàn)的呢炼邀，下一篇就來介紹:)
如果有什么疑問，也歡迎留言剪侮。
以上~
