Scalaz（24）－ 泛函資料結構： Tree-資料遊覽及維護

上節我們讨論了zipper－串形不可變集合（immutable sequential collection）遊标，在串形集合中左右遊走及元素維護操作。這篇我們談談tree。在電子商務應用中對于xml,json等格式檔案的處理要求非常之普遍，scalaz提供了tree資料類型及相關的遊覽及操作函數能更友善高效的處理xml,json檔案及系統目錄這些樹形結構資料的相關程式設計。scalaz tree的定義非常簡單：scalaz/tree.scala

tree是由一個a值rootlabel及一個流中子樹stream[tree[a]]組成。tree可以隻由一個a類型值rootlabel組成，這時流中子樹subforest就是空的stream.empty。隻有rootlabel的tree俗稱葉（leaf），有subforest的稱為節（node）。scalaz為任何類型提供了leaf和node的建構注入方法：syntax/treeops.scala

實際上注入方法調用了tree裡的建構函數：

tree提供了建構和模式拆分函數：

我們可以直接建構tree：

tree實作了下面衆多的接口函數：

那麼tree就是個monad，也是functor,applicative，還是traversable,foldable。tree也實作了order,equal執行個體，可以進行值的順序比較。我們就用些例子來說明吧： 

說到建構tree，偶然在網上發現了這麼一個tree建構函數：

據說這個pathtree函數能把list裡的目錄結構轉化成tree。先看看到底是不是具備如此功能：

果然能行，而且還能把"b"節點合并彙集。這個函數的作者簡直就是個神人，起碼是個算法和fp文法運用大師。我雖然還無法達到大師的程度能寫出這樣的泛函程式，但好奇心是擋不住的，總想了解這個函數是怎麼運作的。可以用一些測試資料來逐漸跟蹤一下： 

通過上面的跟蹤約化我們看到list(list(a))在pathtree裡的執行過程。這裡把複雜的groupby和collect函數的用法和結果了解了。實際上整個過程相當于：

如果再增加一個點就相當于：

加多一層： 

 合并目錄：

相信這些跟蹤過程足夠了解整個函數的工作原理了。

有了tree建構方法後就需要tree的遊動和操作函數了。與串形集合的直線遊動不同的是，樹形集合遊動方式是分岔的。是以zipper不太适用于樹形結構。scalaz特别提供了樹形集合的定位遊标treeloc，我們看看它的定義：scalaz/treeloc.scala

樹形集合遊标treeloc由目前節點tree、左子樹lefts、右子樹rights及父樹parents組成。lefts,rights,parents都是在流中的樹形stream[tree[a]]。

用tree.loc可以直接對目标樹生成treeloc：

treeloc的遊動函數：

我們試着用這些函數遊動：

跳動函數：

find用法示範：

注意：上面6個跳動都成功了。如果無法跳轉結果會是none

insert,modify,delete這些操作函數：

用法示範：

settree和delete會替換目前節點下的所有子樹：

<a></a>

通過scalaz的tree和treeloc資料結構，以及一整套樹形結構遊覽、操作函數，我們可以友善有效地實作fp風格的不可變樹形集合程式設計。