泛函程式設計（6）－資料結構－List基礎

    list是一種最普通的泛函資料結構，比較直覺，有良好的示範基礎。list就像一個管子，裡面可以裝載一長條任何類型的東西。如需要對管子裡的東西進行處理，則必須在管子内按直線順序一個一個的來，這符合泛函程式設計的風格。與其它的泛函資料結構設計思路一樣，設計list時先考慮list的兩種狀态：空或不為空兩種類型。這兩種類型可以用case class 來表現:

以上是一個可以裝載a類型元素的list，是一個多态的類型（polymorphic type）。+a表示list是協變（covariant）的，意思是如果apple是fruit的子類（subtype）那麼list[apple]就是list[fruit]的子類。nil繼承了list[nothing],nothing是所有類型的子類。結合協變性質，nil可以被視為list[int],list[string]...

list的另一種實作方式：

以上代碼中empty,cons兩個方法可以實作list的兩個狀态。

我們還是采用第一種實作方式來進行下面有關list資料運算的示範。第二種方式留待stream的具體實作示範說明。

先來個list自由建構器：可以用list(1,2,3)這種形式建構list: 

說明：使用了遞歸算法來處理可變數量的輸入參數。apply的傳入參數as是個數組array[a]，我們使用了scala标準集合庫array的方法:as.head, as.tail。示範如下： 

增加了apply方法後示範一下list的構成：

與以下方式對比，寫法簡潔多了：

再來試一個運算：計算list[int]裡所有元素的和，還是用模式比對和遞歸方式來寫：

我們把sum的實作放到特質申明裡就可以用以下簡潔的表達方式了：

再試着玩多态函數sum:

現在可以分别試試list[int]和list[string]:

以下是一些list常用的函數： 

看看以上的這些函數；是不是都比較相似？那是因為都是泛函程式設計風格的原因。主要以模式比對和遞歸算法來實作。以下是使用示範：

試試把一個list拼在另一個list後面：

隻是想試試scala的簡潔表達方式。

噢，漏了兩個：

下面把幾個泛函資料結構通用的函數實作一下：

這幾個函數有多種實作方法,使scala for-comprehension對支援的資料結構得以實作。有關這幾個函數在泛函程式設計裡的原理和意義在後面的有關functor,applicative,monad課題裡細說。