<script src='stream-min.js'></script>
壓縮後僅 2Kb,完全獨立。
Stream 是一種操作起來很像陣列或鏈結串列的資料結構,但多了一些特別的能力。
特別在哪裡?和陣列不同,stream 可以承載無限多的元素。這份魔力來自「延後求值」(lazily evaluated)——元素不是事先算好放著,而是需要時才算出來。
如果你願意花十分鐘讀完這篇,你對程式設計的觀感很可能被改寫(除非你本來就寫函數式語言)。
Stream 是容器,用 Stream.make 就能裝入元素:
var s = Stream.make( 10, 20, 30 ); // s is now a stream containing 10, 20, and 30
此時 s 是一個含 3 個元素、有順序的 stream。用 s.length() 看長度,s.item(i) 按索引取值,s.head() 取第一個元素:
var s = Stream.make( 10, 20, 30 ); console.log( s.length() ); // outputs 3 console.log( s.head() ); // outputs 10 console.log( s.item( 0 ) ); // exactly equivalent to the line above console.log( s.item( 1 ) ); // outputs 20 console.log( s.item( 2 ) ); // outputs 30
本頁已載入這個類庫,把上面幾行貼進瀏覽器的 JavaScript 控制台就能直接跑。
也可以用 new Stream() 或 Stream.make() 建出空 stream。s.tail() 回傳「除頭元素之外其餘元素」組成的新 stream;對空 stream 呼叫 head() 或 tail() 會拋出異常;s.empty() 用來判斷是否為空。
var s = Stream.make( 10, 20, 30 ); var t = s.tail(); // returns the stream that contains two items: 20 and 30 console.log( t.head() ); // outputs 20 var u = t.tail(); // returns the stream that contains one item: 30 console.log( u.head() ); // outputs 30 var v = u.tail(); // returns the empty stream console.log( v.empty() ); // prints true
手動遍歷:
var s = Stream.make( 10, 20, 30 );
while ( !s.empty() ) {
console.log( s.head() );
s = s.tail();
}
或者直接用 s.print()。Stream.range( min, max ) 則會產生一段連續自然數:
var s = Stream.range( 10, 20 ); s.print(); // prints the numbers from 10 to 20
s.map( f ) 用 f 處理每個元素,回傳處理後的新 stream:
function doubleNumber( x ) { return 2 * x; }
var numbers = Stream.range( 10, 15 );
numbers.print(); // prints 10, 11, 12, 13, 14, 15
var doubles = numbers.map( doubleNumber );
doubles.print(); // prints 20, 22, 24, 26, 28, 30
s.filter( f ) 只保留讓 f 回傳 true 的元素:
function checkIfOdd( x ) {
if ( x % 2 == 0 ) { return false; } // even number
else { return true; } // odd number
}
var numbers = Stream.range( 10, 15 );
numbers.print(); // prints 10, 11, 12, 13, 14, 15
var onlyOdds = numbers.filter( checkIfOdd );
onlyOdds.print(); // prints 11, 13, 15
s.walk( f ) 對每個元素執行 f,但不改變 stream 本身:
function printItem( x ) { console.log( 'The element is: ' + x ); }
var numbers = Stream.range( 10, 12 );
numbers.walk( printItem );
// The element is: 10
// The element is: 11
// The element is: 12
s.take( n ) 取出前 n 個元素組成新 stream,是截斷無限流的關鍵:
var numbers = Stream.range( 10, 100 ); // numbers 10...100 var fewerNumbers = numbers.take( 10 ); // numbers 10...19 fewerNumbers.print();
另有 s.scale( factor ) 對每個元素乘以因子,s.add( t ) 把兩個 stream 對位相加:
var numbers = Stream.range( 1, 3 ); var multiplesOfTen = numbers.scale( 10 ); multiplesOfTen.print(); // prints 10, 20, 30 numbers.add( multiplesOfTen ).print(); // prints 11, 22, 33
雖然例題都是數字,但 stream 裡可以放字串、布林值、函式、物件,甚至陣列與其他 stream。唯一不行的是 null 與 undefined。
不需要真的塞入無限多元素。在 Stream.range( low, high ) 中省略第二個參數,就變成「從 low 到無限」;連 low 也省略時預設從 1 開始,也就是全部自然數。
這會耗盡記憶體嗎?不會,而且跑得跟陣列一樣快:
var naturalNumbers = Stream.range(); // returns the stream containing all natural numbers from 1 and up var oneToTen = naturalNumbers.take( 10 ); // returns the stream containing the numbers 1...10 oneToTen.print();
老實說,嚴格意義上它並不是真的無限,但你可以「當它是無限」來思考,這就換來了一種更貼近數學語言、也更接近自然描述的程式風格。這個類庫本身就是照這個思路設計的。
var naturalNumbers = Stream.range(); // naturalNumbers is now 1, 2, 3, ...
var evenNumbers = naturalNumbers.map( function ( x ) { return 2 * x; } ); // 2, 4, 6, ...
var oddNumbers = naturalNumbers.filter( function ( x ) { return x % 2 != 0; } ); // 1, 3, 5, ...
evenNumbers.take( 3 ).print(); // prints 2, 4, 6
oddNumbers.take( 3 ).print(); // prints 1, 3, 5
new Stream() 建空流;new Stream( head, functionReturningTail ) 建非空流——第一個參數是頭元素,第二個參數是一個函式,呼叫它才會得到尾部 stream。
var s = new Stream( 10, function () {
return new Stream();
} );
// the head of the s stream is 10; the tail of the s stream is the empty stream
s.print(); // prints 10
var t = new Stream( 10, function () {
return new Stream( 20, function () {
return new Stream( 30, function () {
return new Stream();
} );
} );
} );
t.print(); // prints 10, 20, 30
這樣寫比 Stream.make( 10, 20, 30 ) 囉嗦,但威力在於可以輕鬆造出無限流:
function ones() {
return new Stream(
// the first element of the stream of ones is 1...
1,
// and the rest of the elements of this stream are given by calling ones() (this same function!)
ones
);
}
var s = ones(); // now s contains 1, 1, 1, 1, ...
s.take( 3 ).print(); // prints 1, 1, 1
這也解釋了第二參數為何必須是函式而非尾部本身:只有延遲求值,才不會在構造階段就陷入無盡迴圈。
同樣技巧可以造出自然數:
function ones() { return new Stream( 1, ones ); }
function naturalNumbers() {
return new Stream(
// the natural numbers are the stream whose first element is 1...
1,
function () {
// and the rest are the natural numbers all incremented by one,
// obtained by adding the stream of natural numbers 1, 2, 3, 4, 5, ...
// to the infinite stream of ones 1, 1, 1, 1, 1, ...
// yielding 2, 3, 4, 5, 6, ... which are the REST of the natural numbers after one
return ones().add( naturalNumbers() );
}
);
}
naturalNumbers().take( 5 ).print(); // prints 1, 2, 3, 4, 5
對無限流呼叫 s.print() 會永不停止直到耗盡記憶體,s.length() 會陷入無盡循環,s.walk( f ) 同樣不適用。map 與 filter 可以,但取用時務必先 take( n ) 取出有限部分。
function sieve( s ) {
var h = s.head();
return new Stream( h, function () {
return sieve( s.tail().filter( function( x ) {
return x % h != 0;
} ) );
} );
}
sieve( Stream.range( 2 ) ).take( 10 ).print();
這段在做什麼?建議逐步推:先找出輸出的頭元素,再找第二個(也就是尾部的頭元素),然後第三、第四個。函式名稱也是提示。除非有函數式程式設計經驗,多數人第一眼看不出來——看不出來是正常的,把它跑一遍,答案會自己浮現。
Stream 並不是新點子。許多函數式語言早有類似特性:「stream」這個名字來自 Scheme(LISP 的一支方言),Haskell 則稱之為無限列表,而 take、tail、head、map、filter 這些命名正取自 Haskell。Python 等語言也有相近但不同的概念,通稱為「生成器」(generators)。
這些想法在函數式社群流傳已久,但對多數 JavaScript 開發者仍是新鮮事。本頁許多例子與創意來自《Structure and Interpretation of Computer Programs》,該書可免費在網上取得,也是我做這個類庫的靈感來源,如果你有興趣,強烈推薦一讀。
如果你偏好其他風格的 stream,可以試試 linq.js;若使用 node.js,node-lazy 可能更合適;若喜歡 CoffeeScript,Michael Blume 正在把它移植成 coffeestream。
這個類庫是免費的。如果你覺得它有用,歡迎寫信告訴我你是哪裡人、做什麼的——我很喜歡收集世界各地的照片,信中不妨附上你城市的一張街景。