泛函程式設計（13）－無窮資料流－Infinite Stream

   上節我們提到stream和list的主要分别是在于stream的“延後計算“（lazy evaluation）特性。我們還讨論過在處理大規模排列資料集時，stream可以一個一個把資料元素搬進記憶體并且可以逐個元素地進行處理操作。這讓我不禁聯想到我們常用的資料搜尋讀取方式了：大量的資料存放在資料庫裡，就好像無窮的資料源頭。我們把資料讀取方式（那些資料庫讀寫api函數）嵌入stream的操作函數内，把資料搜尋條件傳入stream構造器（constructor）中形成一個對資料搜尋操作的描述。這個産生的stream隻有在我們調用符合搜尋條件的資料庫記錄時才會逐個從資料庫中讀取出來。這可是一個非常熟悉的場景，但我們常常會思考它的原理。

    很多時我們都需要無窮資料流（infinite stream），以直接或一些算法方式有規則地重複産生資料。無窮資料流被定義為“反遞歸”（corecursive）的：遞歸的特性是從複雜到簡單并最後終止，而無窮資料流的特性卻是從簡單到複雜并永遠不會終結。

我們先從簡單的無窮資料流開始：數字産生器：

ones函數可以産生一個無窮的資料流。每個元素都是常數1。從這個簡單的例子我們可以稍微領略反遞歸的味道：cons(1,ones),通過重複不斷運算cons來産生無窮資料。

我們可以把一些算法嵌入無窮資料流産生過程：

從以上這些例子可以看出：我們不斷重複的在cons。而cons的參數則是算法的實作結果。

以下的unfold是一個最通用的stream建構函數（stream builder），我們需要做些重點介紹：

unfold的工作原理模仿了一種狀态流轉過程：z是一個起始狀态，代表的是一個類型的值。然後使用者（caller）再提供一個操作函數f。f的款式是：s => option[(a,s)]，意思是接受一個狀态，然後把它轉換成一對新的a值和新的狀态s，再把它們放入一個option。如果option是none的話，這給了使用者一個機會去終止運算，讓unfold停止遞歸。從unfold的源代碼可以看到f(z) match {} 的兩種情況。需要注意的是函數f是針對z這個類型s來操作的，a類型是stream［a]的元素類型。f的重點作用在于把s轉換成新的s。我們用一些例子來說明：

constantbyunfold産生一個無窮的常數：a同時代表了元素類型和狀态。_ => some((a,a))意思是無論輸入任何狀态，元素值和狀态都不轉變，是以unfold會産生同一個數字。另外f的結果永遠不可能是none，是以這是一個無窮資料流（infinite stream）。

再來一個例子：

frombyunfold産生一個從s開始的無窮整數序列：s 同時代表了元素類型和狀态。_ => some((s,s+1))表示新a值是s,新狀态是s+1，是以新s = s + 1。狀态轉變原理可以從改變 s+1 到 s+2 運算後産生的結果得以了解：

再試一個不同類型的狀态例子：

在以上的例子裡：s類型為tuple，起始值(0,1)，元素類型a是int。函數f: int => option[(int, int)]。f函數傳回新a=a1, 新狀态s (a2, a1+a2)。由于狀态是個tuple類型，(a1,a2)是個模式比對操作，是以必須加上case。s=(0,1) >>> (a,s)=(0,(1,0+1)) >>>(1,(1,1+1))>>>(1,(2,2+1))>>>(2,(3,2+3))>>>(3,(5,3+5))>>>(5,(8,5+8))>>>(8,(13,8+13))從以上推斷我們可以得出a>>>0,1,1,2,3,5,8,13，而狀态s>>>(0,1),(1,1),(1,2),(2,3),(3,5),(5,8)...不斷變化。

在來個更展現狀态轉變的例子：用unfold實作的map函數 

s類型即uncons類型>>>option[(a, stream[a])], uncons的新狀态是 some((t.head, t.tail))。因為我們采用了資料結構嵌入式的設計，是以必須用uncons來代表stream，它的下一個狀态就是some((t.head, t.tail))。如果使用子類方式cons(h,t)，那麼下一個狀态就可以直接用t來表示，簡潔多了。

 再看看還有什麼函數可以用unfold來實作吧：

風格基本上是一緻的。

寫完這些例子才有時間靜下來想了一下：費了這麼大勁搞這個無窮資料流到底能幹什麼呢？作為資料庫搜尋的資料源嗎，這個可以用普通的stream來實作。由于無窮資料流是根據一些算法有規則的不停頓産生資料，那麼用來搭建測試資料源或者什麼數學統計模式環境道是是可以的。想到不斷産生資料，那麼用來畫些動态的東西也行吧，那在遊戲軟體中使用也有可能了。