這次來說說函數(shù)式的數(shù)據(jù)結構是什么樣子的髓抑，本章會先用一個list來舉例子說明飞蚓，最后給出一個Tree數(shù)據(jù)結構的練習弟跑，放在公眾號里面，練習里面給出了基本的結構悠抹，但代碼是空缺的需要補上珠月，此外還有預留的testcase可以驗證。

關注公眾號：哈爾的數(shù)據(jù)城堡楔敌，回復“函數(shù)式數(shù)據(jù)結構”可以獲得啤挎。（寫文章不容易，大哥大姐關注下吧[哭笑]）

然后是這系列的索引：

Scala函數(shù)式編程指南（一） 函數(shù)式思想介紹

scala函數(shù)式編程（二） scala基礎語法介紹

Scala函數(shù)式編程（三） scala集合和函數(shù)

1.什么是函數(shù)式的數(shù)據(jù)結構

還記得前面說過卵凑，函數(shù)式編程最大的特點是什么嗎庆聘？就是沒有副作用。那么函數(shù)式的數(shù)據(jù)結構自然也是如此勺卢。

無副作用的關鍵是：

1. 一個函數(shù)無論調用多少次伙判，只要輸入?yún)?shù)相同，則結果也必然相同黑忱。
2. 且這個函數(shù)執(zhí)行過程中不會改變程序的任何外部狀態(tài)宴抚，如全局變量，對象的屬性等甫煞。
3. 函數(shù)的結果也不依賴外部狀態(tài)菇曲。

在java中，最經(jīng)典的數(shù)據(jù)結構ArrayList抚吠，是通過一個全局的size變量常潮，來控制ArrayList的大小的，這就說明ArrayList并非無副作用埃跷。

在scala中蕊玷，集合（List邮利，Map等）默認是不可變的，以鏈表List為例垃帅，是無法通過push等操作延届，往一個鏈表里面添加內容的。只能通過兩個鏈表相加的方式贸诚，生成一個新鏈表（Map也是一樣方庭，通過兩個Map相加，Key相同的會覆蓋酱固，以達到更新的目的）械念。這點倒是和String有點像。

不過其實這樣有一個問題运悲，那就是很耗費內存龄减。但這個問題可以用懶加載來解決，限于篇幅班眯，后面再介紹吧希停。

總結一下，函數(shù)式的數(shù)據(jù)結構署隘，最大的特點宠能，就是沒有副作用。那么如何實現(xiàn)無副作用的數(shù)據(jù)結構呢磁餐，我們下面用鏈表的例子來展示违崇。

不過在這之前，需要先回顧下一些語法知識诊霹。

2.scala知識回顧

我的一個觀點是羞延，語言的語法知識如果只是看，背畅哑，而沒有實際用到肴楷，那是比較難記住的。這里就把這次會用到的語法知識做個簡單介紹荠呐，如果有需要赛蔫，可以查閱前面寫的前兩章。

我這里也有演示如果運用前面介紹的語法知識實現(xiàn)一個函數(shù)式的List()泥张。

PS：如果不想看語法知識可以直接跳到第三節(jié)呵恢。

前面的語法索引：

scala函數(shù)式編程（二） scala基礎語法介紹

Scala函數(shù)式編程（三） scala集合和函數(shù)

2.1 scala的模式匹配

模式匹配類似于swtch語法，不過它能匹配的不止是值媚创，還有數(shù)據(jù)類型渗钉。同時，它是一個匿名函數(shù)，在scala里鳄橘，函數(shù)不用return声离，能直接返回值。

val times = 1

//使用模式匹配來匹配值
times match {
  case 1 => "one"
  case 2 => "two"
  case _ => "some other number"
}

//使用模式匹配瘫怜，匹配類型术徊，再判斷值

times match {
  case i:Int if i == 1 => "one"
  case i:Int if i == 2 => "two"
  case _ => "some other number"
}

如果有小伙伴想了解更多，可以看看我這篇鲸湃，scala模式匹配詳細解析赠涮。

2.2 object和apply

前面介紹到，object是一個類的伴生對象暗挑，而且相當于static類笋除，內存里只能有一個對象。apply方法則是說炸裆，可以在使用object對象的時候垃它，直接默認使用。別說了晒衩，看代碼：

scala> class Foo {}
defined class Foo

//有一個apply方法
scala> object FooMaker {
     |   def apply() = new Foo
     | }
defined module FooMaker

//新建object嗤瞎，自動得就調用了apply
scala> val newFoo = FooMaker() //賦值的對象是Foo，因為調用了FooMaker()的apply 
newFoo: Foo = Foo@5b83f762  

上面的代碼听系，F(xiàn)ooMaker相當于一個工廠。

2.3 scala的泛型

scala中的泛型虹菲，叫做型變或變性靠胜，英文叫variance。主要有三種情況：

假設Dog是Animal的子類毕源。那么有如下關系：

• 協(xié)變(covariant)：List[Dog]是List[Animal]的子類浪漠，形態(tài)用一個+號表示，即List[+A]（這里的A是泛指霎褐，類似java中的泛型址愿，可以隨便指定一個字母）。
• 逆變(contravariant)：與協(xié)變相反冻璃，List[Animal]是List[Dog]的子類响谓，形態(tài)用一個-號表示，即List[-A]省艳。
• 不變(invariant)：List[Dog]是List[Animal]的無關娘纷，不用任何表示，List[A]跋炕。

協(xié)變是比較符合正常邏輯思考的赖晶，一群狗確實也可以說是一群動物。逆變就比較反直覺了辐烂，不過這里先不討論這點遏插，后面有機會再討論捂贿。

3.構建函數(shù)式的List

OK，有了上面的基礎胳嘲，就能夠來構建一個函數(shù)式的數(shù)據(jù)結構了眷蜓，不過在此之前，先讓我們回顧下傳統(tǒng)的List數(shù)據(jù)結構胎围。

3.1 傳統(tǒng)的List

還記得以前數(shù)據(jù)結構是怎樣設計的嗎吁系？

傳統(tǒng)的List

最普通的鏈表，通常都是由一個又一個的Node組成白魂，一個Node中存儲數(shù)據(jù)和下一個鏈表的變量汽纤。最后通過一個空值結尾，通常是Null福荸。

在Java中蕴坪，它的鏈表Linklist，是通過一個全局變量size來控制鏈表的敬锐。

通過for循環(huán)實現(xiàn)基礎的增刪查改等操作背传。而是，也是傳統(tǒng)List的常見寫法台夺，但在函數(shù)式的List中可不能這樣径玖。還記得嗎，函數(shù)式最大的特點就是無副作用颤介。像java這里用一個全局的size來控制梳星，那可真是萬萬不可啊，在多線程的情況下還不得崩潰滚朵。

關于為什么要寫無副作用的代碼冤灾，這里就不做探討，詳細內容可以看看這個系列的第一章辕近。Scala函數(shù)式編程指南（一） 函數(shù)式思想介紹韵吨。

3.2 scala實現(xiàn)函數(shù)式的List

我們要做的是寫出無副作用的集合，那要怎么做呢移宅？給5秒鐘閉上眼睛好好想一想有沒有什么思路归粉。。吞杭。

可能有的同學會想得到盏浇，這個答案就是遞歸。通過遞歸芽狗，能夠避免副作用的產生绢掰。如常用的增刪查改，如果使用遞歸，就可以避免使用一個全局變量滴劲，當然遞歸通常都沒有直接使用for循環(huán)那么直觀攻晒，所以充滿遞歸的代碼初次看會比較晦澀。但如果用多了班挖，你會發(fā)現(xiàn)其實函數(shù)式的代碼鲁捏，也是非常好懂的。

下面萧芙，我們來看看如果使用遞歸實現(xiàn)一個List给梅。

3.1 定義基本的類型

首先，我們要定義每個節(jié)點Node的類型双揪，以及結尾Nil动羽。由于使用到了遞歸，我們需要讓Node和Nil都有同樣的父類渔期，因為遞歸函數(shù)的返回都是一樣的运吓。

如果還是不明白為什么要讓Node和Nil為啥要有同樣的父類，那不妨先放一放疯趟，繼續(xù)看下去吧拘哨。

//定義自己的特質（相當于java的接口），泛型使用協(xié)變
sealed trait List[+A]

//定義一個case類信峻，作為每一個List的結尾
case object Nil extends List[Nothing] 

//定義List子類倦青，也可以說是List中的每個Node，每個List都是由一個又一個的Cons組成站欺，以Nil結尾
case class Cons[+A](head: A, tail: List[A]) extends List[A]

注意第一行定義了List[+A]的特質姨夹，和scala集合中的List是區(qū)分開來的，只是名字叫一樣而已矾策。這個是我們自己的List！峭沦！

而后定義了Nil和Cons贾虽，分別作為List的結尾和Node節(jié)點，注意case class也是scala的語法糖吼鱼，可以理解為java bean蓬豁。

之所以先定義了一個List的特質（接口），再分別用Nil和Cons繼承它菇肃，是因為在遞歸的情況下地粪，要讓節(jié)點和結尾保持同一類型，而這個就是通過多態(tài)實現(xiàn)的琐谤。

3.2 實現(xiàn)List工廠

前面說到蟆技，通常是用object來作為工廠，這里也是一樣的，我們可以定義List工廠质礼。

定義工廠方法如下：

object List {
  //使用可變長度旺聚，如果傳進來的參數(shù)是空，就返回Nil眶蕉，否則使用遞歸返回Cons砰粹，注意，這里的apply方法就是使用了遞歸
  def apply[A](as: A*): List[A] = // Variadic function syntax
    if (as.isEmpty) Nil
    else Cons(as.head, apply(as.tail: _*))

}

這里的apply[A](as: A)造挽，括號里面的A的意思碱璃，是多個參數(shù)的意思，就是說可以有很多個參數(shù)饭入，是scala的一個語法糖嵌器。

在最后

else Cons(as.head, apply(as.tail: _*))

看到最后面的 _*了嗎，這個的意思圣拄，是除了第一個參數(shù)以外的其他參數(shù)嘴秸，也是語法糖。

在這一個小小的地方就用到了遞歸庇谆，不斷調用apply方法去解析后面的參數(shù)岳掐，最終生成一個List。初次看可能會比較迷饭耳，可能放在編譯器里面運行一下串述，方便理解。而這種操作在scala函數(shù)式編程中寞肖，是非常普遍的做法纲酗。

至此，我們就建立了一個List的數(shù)據(jù)結構新蟆，先來看看我們的成果

//一個遞歸的List
scala> List(1,2,3)
res0: List[Int] = Cons(1,Cons(2,Cons(3,Nil)))

現(xiàn)在的List數(shù)據(jù)結構只是初具雛形觅赊，我們還得往里面加方法。

3.3 用函數(shù)式的方式實現(xiàn)List更多方法

通常來說琼稻，數(shù)據(jù)結構比較重要的是增刪查改等操作吮螺，但因為是不可變的，同時函數(shù)式中通常是不改變對象信息的帕翻，所以這些基本操作反而不是首要的鸠补。

我們先來看一個簡單些的例子吧，讓一個List[Int]中的數(shù)據(jù)累加嘀掸。

object List {
  ......
  //傳入?yún)?shù)是一個Int類型的List紫岩，使用模式匹配
  def sum(ints: List[Int]): Int = ints match {
    case Nil => 0
    //使用遞歸累加
    case Cons(x,xs) => x + sum(xs)
  }
  ......
}

這里主要傳入的參數(shù)是一個Int類型的List，然后使用模式匹配睬塌，如果是結尾泉蝌，則返回0歇万，如果是中間節(jié)點，則使用遞歸累加梨与。

上面那個例子比較簡單堕花，明白后可以來看看如何為List構建更加通用的方法。通常比較常用的是前面介紹過的諸如map粥鞋，filter等操作缘挽，下面先用一個map來說明一下吧。

object List {
  ......
  //Map操作呻粹，使用模式匹配
  def map[A,B](list: List[A],f: A => B): List[B] =list match {
    case Nil              ? Nil
    //使用遞歸
    case Cons(head, tail) ? Cons(f(head), map(tail,f))
  }
  ......
}

map函數(shù)壕曼，需要傳進入一個待處理的list，以及一個函數(shù)作為參數(shù)等浊，用以對List中每個元素做處理腮郊。

比如說想讓List中每個元素+1，那就可以傳入

val addOne = (num:Int) => num+1

還記得之前說筹燕，在scala中轧飞，函數(shù)也能當作變量嘛。將addOne這個函數(shù)作為參數(shù)撒踪，這樣就會讓List中每個元素都+1过咬，然后返回一個新的List，當然制妄，這個也是用遞歸實現(xiàn)的掸绞。

實現(xiàn)代碼看起來很簡潔，也是用模式匹配耕捞，匹配每個元素的類型衔掸，就是是Node還是結尾。如果是結尾俺抽，直接返回敞映，如果是Node，那么處理完當前數(shù)據(jù)磷斧，遞歸去處理后面的數(shù)據(jù)驱显，并返回新的處理后的Node。

熟悉以后瞳抓，會發(fā)現(xiàn)這樣的處理方式看著很舒服，代碼寫得也很少伏恐，非常簡潔孩哑。

在我看來，這就是遞歸的魅力所在翠桦。

除了map之外横蜒，還有其他操作處理胳蛮，包括filter，foldLeft丛晌，reduce等操作仅炊。我把代碼放在我的公眾號中，限于篇幅這里就不講太多澎蛛。關注公眾號：哈爾的數(shù)據(jù)城堡抚垄，回復“函數(shù)式數(shù)據(jù)結”可以獲得。

代碼中使用了隱式轉換來擴充List的操作谋逻，并演示了如何使用隱式轉換呆馁，以及如何使用復用來組合功能以實現(xiàn)新的功能。有同學可能不明白為什么簡單的List要搞這么復雜毁兆，看了代碼可能會更加理解浙滤。

4.函數(shù)式的二叉搜索樹

這部分我是作為練習的，連同List代碼放在一塊气堕，里面有基本的結構纺腊，但一些缺失的內容需要你來補充。相信我茎芭，做了一遍揖膜，肯定能夠對函數(shù)式的數(shù)據(jù)結構有更深的理解。

對了骗爆，二叉搜索樹的練習還有幾個test case次氨，做完跑一遍了，如果全過那基本上你寫的代碼就不會有太大的問題摘投，good luck~

再說一遍我把練習的代碼放在了我的公眾號中煮寡，關注公眾號：哈爾的數(shù)據(jù)城堡，回復“函數(shù)式數(shù)據(jù)結構”就能免費獲得啦犀呼。

下一篇會再針對List和Tree的代碼來講一講幸撕，有不明白的地方到時候也可以看看。

以上~~

推薦閱讀：
通俗得說線性回歸算法（一）線性回歸初步介紹
通俗得說線性回歸算法（二）線性回歸初步介紹
大數(shù)據(jù)存儲的進化史 --從 RAID 到 Hadoop Hdfs
C外臂，java坐儿，Python，這些名字背后的江湖宋光！