在 Scala 裡面，有一個叫 Stream 的東西，在 Functional Programming 中好像滿常見的，但一直沒有時間去玩他，這幾天花了一些時間試著用 Stream 實作一些大家熟悉的數列出來，順便訓練腦袋瓜子用 Functional Programming 的方式來思考。
什麼是 Stream
所謂的 Stream 就是一個無窮的數列，該數列的下一項，可以從之前的數列中推演出來，要用到多少就算多少，沒用到的部份就不會去計算這樣。
舉一個最簡單的例子，就是自然數數列：我們都知道自然數的下一項，是由目前這一項加一出來。
在我們熟悉的 Java 或 C 等程式語言中，如果要做「加總從 1 開始的自然數數列到第 N 項」這項工作的話，通常我們會借助迴圈的幫助，寫出像下面的程式碼：
// 加總自然數到第 N 項
int sumNatureNumberTo(int n) {
int sum = 0;
// 用一個迴圈開始數自然數
for (int i = 1; i <= n; i++) {
// 然後再把他一直累加到某個變數中
sum = sum + i;
}
return sum;
}
這段程式相當簡單，寫 Java 或 C 語言習慣了的人，應該馬上就能知道這是在做什麼，但這程式也有一些問題存在：
- 函式裡的 Side Effect 非常嚴重，迴圈每執行一次，sum 這個變數就被改動一次，這對於堅持 Functional Programming 的人來說可能會像眼裡進了沙子，欲除之而後快。
- 每次呼叫 sumNatureNumberTo(n) 這個函式時，都要重新計算一次數列中的值。
針對第二點，雖然我們有可能可以事先建立一個 {0, 1, 2, 3, 4, 5, 6, 7....} 這樣的陣列，但問題是你不知道關鍵的 n 會是多少，所以這個方法不是很實際。
當然，在這個列子中重新計算自然數數列不是什麼大問題，但如果是找所有質數的數列這種比較耗時的問題，能夠把之前算過的東西記下來，會讓我們省很多事。
現在回過頭來看看 Scala 中的 Stream 到底是什麼東西唄。
就像上面說的，Stream 事實上就是一個無窮數列，他最重要的關念是他是由以下兩部份組成：
- 數列的開頭的值
- 接下來的數列（的計算方法）
舉一個例子，我們知道自然數的數列是 [1, 2, 3, 4, 5, 6, 7, 8, 9...] 這個樣子，所以我們可以把一個從 N 開始的自然數數列視作如下：
- 從第 1 項開始就是 1 這個數字，加在 [2, 3, 4, 5, 6, 7, 8, 9] 前面
- 從第 2 項開始就是 2 這個數字，加在 [3, 4, 5, 6, 7, 8, 9] 前面
- 從第 3 項開始就是 3 這個數字，加在 [4, 5, 6, 7, 8, 9] 前面
而在 Scala 中要表示這樣的關係，可以用以下兩種方式：
- Stream.cons(目前這一項, 下一項的計算方法)
- 目前這一項 #:: 下一項的計算方法
雖然兩種寫法是等價的，但因為第二種寫法在視覺上比較直覺（就是某個東西接在某個東西之後），所以下面的程式碼會用第二種寫法。
自然數的 Stream
有了這樣的概念之後，我們就可以寫出一個代表自然數的 Stream 出來。
// 計算從 n 開始的自然數數列
def natureNumber(n: Int): Stream[Int] = {
println ("計算第 %d 項" format(n))
// 從 n 開始的自然數數列就是由以下的東西組成：
//
// 1. 開頭是 n
// 2. 後面跟著開頭是從 n+1 開始的自然數
//
n #:: natureNumber(n+1)
}
有了上面的程式，我們就隨時可以建立一個從 n 開始的自然數數列，而這個數列會隨著我們使用自己長大。
如果我們要計算前 10 項還有前 20 項的合，那麼我們只要用下面的程式碼就可以了：
// 建立一個從 1 開始的自然數數列
val fromOne = natureNumber(1)
// take(10) ==> 取出前十項
// reduceLeft(_ + _) ==>
//
// 將數列開頭的前兩項相加後取代掉數列中的前兩項，然後不斷執行下去，直到最後一個數字
// 舉例來說：
// x = List(1, 2, 3, 4, 5).reduceLeft(_ + _) 的計算過程是：
// x = List(3, 3, 4, 5)
// x = List(6, 4, 5)
// x = List(10, 5)
// x = List(15)
// x = 15
println (fromOne.take(10).reduceLeft(_ + _))
// 偷懶的寫法
println (fromOne.take(20).sum)
執行上面的程式碼，會出現如下的結果：
brianhsu@USBGentoo ~ $ scala test.scala
計算第 1項
計算第 2項
...
計算第 10項
55
計算第 11項
計算第 12項
...
計算第 20項
210
其中值得注意的一點當我們執行 fromOne.take(20).sum 這行程式碼的時候，我們是從第 11 項開始計算，前十項因為已經計算過了，所以會被 cache 起來，可以直接拿到。
階乘的 Stream
有了上面的概念，我們就可以用 Stream 來實作一個階乘的表，讓我們寫出一個像是查表法的程式，但實際上這個表只有在第 N 項真的有被用到的時候才去計算。
同樣的，要實作階乘的 Stream，我們要先知道階乘的算法：N! = 1 * 2 * ... * n = (N-1)! * n
換句話說，第 N+1 階的階乘，就是 N 階的階乘的值，再乘上 N + 1
// 要計算目前這一階，我們要知道前一階的數字 (prev) 和
// 目前是第幾階 (pos)
def factoral(prev: BigInt, pos: Int): Stream[BigInt] = {
// 目前這一階的值就是前一階乘上現在是第幾階
val current = prev * pos
// 而從第 N 階開始的階乘數列，就是目前這一階的數字，
// 再加上從 N + 1 階開始的階乘數列
current #:: factoral(current, pos + 1)
}
// 我們知道階乘的第一項是 1 * 1
val fTable = factoral(1, 1)
// 看起來像查表法，但實際上是算出來的
println (fTable(3))
println (fTable(4))
println (fTable(10))
// 但因為 5! 在計算 10! 的時候用算過了，所以現在真的是查表
println (fTable(5))
費氏數列的 Stream
OK，下面是最後一個費氏數列的例子，因為概念其實都差不多，所以就直接看程式碼唄。
def createFibStream(): Stream[Int] = {
def fib(x1: Int, x2: Int): Stream[Int] = {
// 目前這一項是前兩項相加
val current = x1 + x2
println("Calculating %d + %d = %d" format(x1, x2, current))
// 費式數列的下一項是前一項(x2) 加目前的這一項(current)
current #:: fib(x2, current)
}
// 費氏數列的第一項固定為 0
0 #:: fib(0, 1)
}
val myFib = createFibStream()
// 只有第一次時會跑出 Calculating 的訊息，計算過後會被 cache 住
println (myFib.take(10).mkString(","))
println (myFib.take(20).mkString(","))
println (myFib.take(20).mkString(","))
// Project Euler 第二題的解法
//
// 問題：
//
// Find the sum of all the even-valued terms in the Fibonacci
// sequence which do not exceed one million
//
// 解法白話文：
//
// 濾出 (filter) 費式數列中為偶數的數字，然後從這個數列中一直取
// 出數字，直到該數字大於 1000000 (takeWhile(_ <= 1000000))，
// 之後再加總取出的數字(sum)
//
println( myFib.filter(_ % 2 == 0).takeWhile(_ <= 1000000).sum )
以上就是 Stream 的簡易用法，當你需要一個可以 cache，但又希望真的有用到才去計算的數列表時，別忘了 Stream 這個好碰友喔。
回響