Scala講座：函數(shù)式編程處理樹結(jié)構(gòu)數(shù)據(jù)

作者：牛尾剛 2009-09-27 15:23:00

本文繼續(xù)Scala講座第七篇的第四部分內(nèi)容，本部分提供了函數(shù)式編程的比較高階一點(diǎn)的案例。

在學(xué)習(xí)完函數(shù)式編程的思考方法之后，嘗試一下更高級(jí)的例子吧。這次考慮一下處理類似于XML的樹結(jié)構(gòu)數(shù)據(jù)的程序。既不使用循環(huán)也不使用變量如何來描述復(fù)雜的處理呢？

先出一個(gè)處理XML數(shù)據(jù)的題目。例如有如下的XML數(shù)據(jù)，有目錄和文件，目錄下有目錄和文件兩種元素。

< xml> 
< dir name="com"> 
< dir name="mamezou"> 
< file name="aaa.txt">< /file> 
< file name="bbb.txt">< /file> 
< /dir> 
< file name="ccc.txt">< /file> 
< /dir> 
< file name="ddd.txt">< /file> 
< /xml>

題目的內(nèi)容是從中取出文件的部分，并打印出文件名。程序的執(zhí)行結(jié)果因該如下：

file:aaa.txt  
file:bbb.txt  
file:ccc.txt  
file:ddd.txt

好，會(huì)變成怎樣的程序呢？另外，Scala有非常強(qiáng)大的XML處理功能，以上的功能實(shí)際上只要一兩行程序就可以完成了。但是這次為了說明函數(shù)式編程，特地不使用哪些功能，而使用簡(jiǎn)單功能來從頭開始編碼。

Scala中XML語句可以作為語言文本（Literal）像數(shù)字和字符串一樣被處理。像下面這樣

scala> val xml = < xml> 
| < dir name="com"> 
| < dir name="mamezou"> 
| < file name="aaa.txt">< /file> 
| < file name="bbb.txt">< /file> 
| < /dir> 
| < file name="ccc.txt">< /file> 
| < /dir> 
| < file name="ddd.txt">< /file> 
| < /xml> 
xml: scala.xml.Elem =  
< xml> 
< dir name="com"> 
：（以下略）

沒有雙引號(hào)，一開始就寫XML文本，然后將其賦值給變量（這里是xml）。他的類型是scala.xml.Elem，父類型為scala.xml.Node，表示XML的標(biāo)記。在這里包含在< xml>< /xml>標(biāo)記對(duì)中的內(nèi)容被綁定在變量xml上。該Node類型里有名為child的方法，返回該標(biāo)記的所有子元素。例如，這里xml.child將返回以如下兩個(gè)標(biāo)記為成員的類似于ArrayBuffer的數(shù)組對(duì)象。

< dir name="com"> 
:  
< /dir>

和

< file name="ddd.txt"/>

這里可以認(rèn)為ArrayBuffer是列表一樣的東西。進(jìn)一步調(diào)用子元素的child方法則可以得到再下一層的元素。調(diào)用。< dir name="com">標(biāo)簽對(duì)象的child方法將返回緊鄰該標(biāo)簽的子元素（目錄標(biāo)記）。

僅使用這個(gè)方法該如何寫取得文件名的程序呢？如果是面向?qū)ο蠓绞剑瑒t可以首先定義Dir類和File類，然后定義Dir和File類的抽象父類Node，然后沿著樹結(jié)構(gòu)定義showFiles方法，然后遞歸調(diào)用該方法來取得文件名。也就是所謂的組合模式（圖１）。

Scala講座圖1：組合模式

如果放棄面向?qū)ο蠖紤]純粹的命令式方法的話就會(huì)很頭疼了。因?yàn)橹挥胒or語句的話，對(duì)于每一個(gè)Dir都要用一個(gè)for循環(huán)，層次一多將會(huì)將會(huì)變得很復(fù)雜，這里省略了命令式方法的實(shí)現(xiàn)。

接下來用函數(shù)式方法來考慮一下。函數(shù)式的情況下，因?yàn)榭紤]的是對(duì)于各個(gè)元素應(yīng)用函數(shù)，先從***元素開始考慮應(yīng)用什么函數(shù)。這個(gè)函數(shù)功能是“在某一時(shí)刻返回某一元素下的文件列表”。這樣就可以想到，那元素如果是file則可直接返回包含該file的列表，如果是Dir的話則返回包含所有子文件的列表。先來看看該函數(shù)的實(shí)例。

def fileFinder(node:scala.xml.Node):List[scala.xml.Node] = node.label match {  
case "xml" => node.child.toList.flatMap(fileFinder)  
case "dir" => node.child.toList.flatMap(fileFinder)  
case "file" => List(node)  
case _ => List()  
}

其中toList()方法為將類列表對(duì)象(ArrayBuffer)轉(zhuǎn)換為列表對(duì)象。剛才用的是類似于ArrayBuffer類的對(duì)象，這里將其轉(zhuǎn)換為標(biāo)準(zhǔn)列表后再操作，而node.label則返回XML標(biāo)記的名稱。

這里開始是正題了，除了file和無匹配處理（case _ => List（））部分，xml和dir處理部分是問題的關(guān)鍵，也就是node.child.toList.flatMap(fileFinder)部分。如果這里關(guān)注的是Node對(duì)象，那處理過程因該是這樣的，首先用child方法取出Node的所有子元素，然后用前面說明過的類似于map的函數(shù)對(duì)每一個(gè)子元素應(yīng)用fileFinder方法并遞歸重復(fù)這一過程。那為什么這樣編碼之后就能得到Node下的所有file元素了呢？

那么flatMap原本的功能又是什么呢？讓我們將其轉(zhuǎn)換成map函數(shù)，然后看一下執(zhí)行過程。將XML的結(jié)構(gòu)簡(jiǎn)單化之后將如下所示

< xml> ←這里  
< dir> 
< dir> 
< file name="aaa.txt"/> 
< file name="bbb.txt"/> 
< /dir> 
< file name="ccc.txt"/> 
< /dir> 
< file name="ddd.txt"/> 
< /xml>

假如現(xiàn)在的要素位置是xml標(biāo)記，將其子元素轉(zhuǎn)換成列表后對(duì)其各個(gè)項(xiàng)目應(yīng)用函數(shù)。

List(fileFinder(< dir>～< /dir>), fileFinder(< file …/>))

file的話保持原樣，如果是dir則對(duì)其子元素應(yīng)用函數(shù)。

List(List(fileFinder(< dir>～< /dir>),fileFinder(< file name="ccc.txt"/>)),List(< file name="ddd.txt">))

接著對(duì)于***個(gè)Node元素應(yīng)用函數(shù)。

List(List(List(< file name="aaa.txt"/>,< file name="bbb.txt"/>), List(< file name="ccc.txt"/>)), List(< file name="ddd.txt">))

理解上述工作過程是比較困難的，重要的是在我的腦中考慮的并不是這樣復(fù)雜的邏輯，而僅僅是實(shí)現(xiàn)“從一個(gè)Node元素中取出file列表”的函數(shù)的邏輯。這需要一定程度的思路切換，考慮用命令式方法來實(shí)現(xiàn)時(shí)實(shí)際上花了我2-3小時(shí)，而想到這個(gè)函數(shù)式方法后不到10分鐘就想通了。

感覺上好像已經(jīng)完成了，但是這還不夠。剛才用map來假想的過程完成后，得到的是List里面還有List的一個(gè)復(fù)合結(jié)構(gòu)，光這樣還不能被使用。那么，flatMap函數(shù)就出場(chǎng)了。這個(gè)函數(shù)在Scala的機(jī)制上具有同map函數(shù)同等的重要層度，將map和flatMap說成Scala函數(shù)機(jī)制的核心都不為過分。

“flatMap “函數(shù)對(duì)每一個(gè)元素應(yīng)用函數(shù)參數(shù)之后將其結(jié)果以列表形式返回，這時(shí)返回結(jié)果是列表類型是關(guān)鍵。接著看一下簡(jiǎn)單的例子吧

首先是map函數(shù)的例子。對(duì)于內(nèi)容為“1，2，3，4，5 “的列表，應(yīng)用x*2函數(shù)。

scala> List(1,2,3,4,5)  
res134: List[Int] = List(1, 2, 3, 4, 5)  
scala> res134.map(x => x * 2)  
res135: List[Int] = List(2, 4, 6, 8, 10)

結(jié)果是List(2, 4, 6, 8, 10)，即將每一個(gè)元素乘以2。題外話，還有一個(gè)叫做filter的函數(shù)，他返回過濾結(jié)果。

scala> res134.filter(x => x != 3)  
res136: List[Int] = List(1, 2, 4, 5)這里是返回3以外的元素。那么，接下來對(duì)于List(1, 2, 3, 4, 5)應(yīng)用如下函數(shù)。  
x => x match {  
case 3 => List(3.1, 3.2, 3.3)  
case _ => List(x * 2)  
}

也就是，3以外的情況下使元素值翻倍，3的時(shí)候?qū)⒃胤指顬椤?.1, 3.2, 3.3“。因此，表面上對(duì)于List(1,2,3,4,5)適用該函數(shù)后希望返回的是List(1, 2, 3.1, 3.2, 3.3, 4, 5)，但用了map函數(shù)后實(shí)際上不是。

scala> res134.map(x => x match {  
| case 3 => List(3.1, 3.2, 3.3)  
| case _ => x * 2 
| })  
res138: List[Any] = List(2, 4, List(3.1, 3.2, 3.3), 8, 10)

結(jié)果中的確包含了3.1, 3.2, 3.3，但是以List中包含List為形式的。這樣只完成了一半，同前面的XML處理一樣現(xiàn)象。那么，使用一下flatMap函數(shù)吧。

scala> res134.flatMap(x => x match {  
| case 3 => List(3.1, 3.2, 3.3)  
| case _ => List(x * 2)  
| })  
res139: List[AnyVal] = List(2, 4, 3.1, 3.2, 3.3, 8, 10)

噢！就是想要的結(jié)果。不僅包含了希望的元素，還將所有元素平攤成了一個(gè)列表。

Scala講座圖2：組合模式flatMap函數(shù)概念圖

回到XML的例子中，正因?yàn)橛胒latMap函數(shù)代替了map函數(shù)，所以對(duì)于< xml>和< dir>部分來說，原本在遞歸調(diào)用中返回的是List，但是flatMap函數(shù)將其互相合并，攤平為單一列表了。

scala> def fileFinder(node:scala.xml.Node):List[scala.xml.Node] = node.label match {  
case "xml" => node.child.toList.flatMap(fileFinder)  
case "dir" => node.child.toList.flatMap(fileFinder)  
case "file" => List(node)  
case _ => List()}  
fileFinder: (scala.xml.Node)List[scala.xml.Node]  
scala> fileFinder(xml).foreach(x => println("file:" + x.attribute("name").getOrElse("")))  
file:aaa.txt  
file:bbb.txt  
file:ccc.txt  
file:ddd.txt

正如所愿的結(jié)果就一下子得到了，函數(shù)式編程真是恐怖呀！這次學(xué)的map和flatMap函數(shù)在Scala中有非常重要的意義。這可以說是函數(shù)式編程的一個(gè)高潮，理解了這個(gè)之后領(lǐng)悟的大門就可以說向你敞開了。這實(shí)際上還與單子（monado）這一思考方法有關(guān)，理解了map和flatMap函數(shù)之后可以說是踏出了完全掌握該思考方法的一大步。關(guān)于“單子”在本連載中還會(huì)著重說明。

【編輯推薦】