新的JavaScript資料結構Streams

最近在網路上看到了一個新的Javascript 小程式——Streams，起初以為是一個普通的Javascript 類別庫，但讀了關於它的介紹後，我發現，這不是一個簡單的類別庫，而且作者的重點也不是這個類別庫的功能，而是－－借用文中的一段話：如果你願意花10分鐘的時間來閱讀這篇文章，你對程式設計的認識有可能會被完全的改變(除非你有函數式程式設計的經驗！

還有：Streams 其實不是一個新的想法。很多的函數式的程式語言都支援這種特徵。所謂‘stream’是 Scheme 語裡的叫法，Scheme 是 LISP 語的一種方言。 Haskell 語言也支援無限大列表(list)。這些’take’，'tail’， ‘head’， ‘map’ 和 ‘filter’ 名字都來自於 Haskell 語言。 Python 和其它很多中語言中也存在雖然不同但很相似的這種概念，它們都被稱作」發生器(generators)」。這些思想來函數式程式設計社群裡已經流傳了很久了。然而，對於大多數的 Javascript 程式設計師來說卻是一個很新的概念，特別是那些沒有函數式程式設計經驗的人。

stream.js

stream.js 是一個很小、完全獨立的Javascript類別庫（僅2k），它為你提供了一個新的Javascript資料結構：streams.

<script src=&#39;stream-min.js&#39;></script>

streams是什麼？ Streams 是一個操作簡單的資料結構，很像數組或連結表，但附加了一些非凡的能力。

它們有什麼特別之處？跟陣列不一樣，streams是一個有魔法的資料結構。它可以裝載無限的元素。是的，你沒聽錯。他的這種魔力來自於具有延後(lazily)執行的能力。這簡單的術語完全能表明它們可以載入無窮多的元素。

下載stream

入門

如果你願意花10分鐘的時間來閱讀這篇文章，你對程式設計的認識有可能會被完全的改變(除非你有函數式程式設計的經驗！)。請稍有耐心，讓我來先介紹streams支援的跟數組或連結表很類似的基本功能操作。然後我會像你介紹一些它所具有的非常有趣的特性。

Stream 是一種容器。它能容納元素。你可以使用 Stream.make 來讓一個stream載入一些元素。只要把想要的元素當成參數傳進去：

// s is now a stream containing 10, 20, and 30
var s = Stream.make( 10, 20, 30 );

夠簡單吧，現在 s 是一個擁有3個元素的stream： 10, 20, and 30; 有順序的。我們可以使用 s.length() 來查看這個stream的長度，用 s.item( i ) 透過索引取出裡面的某個元素。你也可以透過呼叫 s.head() 來獲得這個stream 的第一個元素。讓我們實際操作一下：

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

我們也可以使用 new Stream() 或 直接使用 Stream.make() 來建構一個空的stream。你可以使用 s.tail() 方法來取得stream裡除了頭個元素外的餘下所有元素。如果你在一個空stream上呼叫 s.head() 或 s.tail() 方法，會拋出一個例外。你可以使用 s.empty() 來檢查一個stream是否為空，它會傳回 true 或 false。

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

這樣做可以列印出一個stream裡的所有元素：

var s = Stream.make( 10, 20, 30 );  
while ( !s.empty() ) {  
    console.log( s.head() );  
    s = s.tail();  
}

我們有個簡單的方法來實現這個： s.print() 將會列印出stream裡的所有元素。

用它們還能做什麼？

另一個簡單的功能是 Stream.range( min, max ) 函數。它會傳回一個包含從 min 到 max 的自然數的stream。

var s = Stream.range( 10, 20 );  
s.print(); // prints the numbers from 10 to 20

在這個stream上，你可以使用 map, filter, 和 walk 等功能。 s.map( f ) 接受一個參數 f，它是一個函數， stream裡的所有元素都會被f處理一遍；它的回傳值是經過這個函數處理過的stream。所以，舉個例子，你可以用它來完成讓你的 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，是一個函數，stream裡的所有元素都會經過這個函數處理；它的回傳值也是個stream，但只包含能讓f函數傳回true的元素。所以，你可以用它來過濾到你的stream裡某些特定的元素。讓我們來用這個方法在先前的stream基礎上建構一個只包含奇數的新stream：

function checkIfOdd( x ) {  
    if ( x % 2 == 0 ) {  
        // even number  
        return false;  
    }  
    else {  
        // odd number  
        return true;  
    }  
}  
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里的所有元素都要经过这个函数处理，但它并不会对这个stream做任何的影响。我们打印stream里所有元素的想法有了新的实现方法：

function printItem( x ) {  
    console.log( 'The element is: ' + x );  
}  
var numbers = Stream.range( 10, 12 );  
// prints:  
// The element is: 10  
// The element is: 11  
// The element is: 12  
numbers.walk( printItem );

还有一个很有用的函数： s.take( n )，它返回的stream只包含原始stream里第前n个元素。当用来截取stream时，这很有用：

var numbers = Stream.range( 10, 100 ); // numbers 10...100  
var fewerNumbers = numbers.take( 10 ); // numbers 10...19  
fewerNumbers.print();

另外一些有用的东西：s.scale( factor ) 会用factor(因子)乘以stream里的所有元素； s.add( t ) 会让 stream s 每个元素和stream t里对应的元素相加，返回的是相加后的结果。让我们来看几个例子：

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。然而，请注意一定，stream里不能装载一些特殊的值：null 和 undefined。

想我展示你的魔力！

现在，让我们来处理无穷多。你不需要往stream添加无穷多的元素。例如，在Stream.range( low, high )这个方法中，你可以忽略掉它的第二个参数，写成 Stream.range( low )， 这种情况下，数据没有了上限，于是这个stream里就装载了所有从 low 到无穷大的自然数。你也可以把low参数也忽略掉，这个参数的缺省值是1。这种情况中，Stream.range()返回的是所有的自然数。

这需要用上你无穷多的内存/时间/处理能力吗？不，不会。这是最精彩的部分。你可以运行这些代码，它们跑的非常快，就像一个普通的数组。下面是一个打印从 1 到 10 的例子：

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();

关键是你可以把这些结构想成无穷大，这就引入了一种新的编程范式，一种致力于简洁的代码，让你的代码比通常的命令式编程更容易理解、更贴近自然数学的编程范式。这个Javascript类库本身就很短小；它是按照这种编程范式设计出来的。让我们来多用一用它；我们构造两个stream，分别装载所有的奇数和所有的偶数。

var naturalNumbers = Stream.range(); // naturalNumbers is now 1, 2, 3, ...  
var evenNumbers = naturalNumbers.map( function ( x ) {  
    return 2 * x;  
} ); // evenNumbers is now 2, 4, 6, ...  
var oddNumbers = naturalNumbers.filter( function ( x ) {  
    return x % 2 != 0;  
} ); // oddNumbers is now 1, 3, 5, ...  
evenNumbers.take( 3 ).print(); // prints 2, 4, 6  
oddNumbers.take( 3 ).print(); // prints 1, 3, 5

很酷，不是吗？我没说大话，stream比数组的功能更强大。现在，请容忍我几分钟，让我来多介绍一点关于stream的事情。你可以使用 new Stream() 来创建一个空的stream，用 new Stream( head, functionReturningTail ) 来创建一个非空的stream。对于这个非空的stream，你传入的第一个参数成为这个stream的头元素，而第二个参数是一个函数，它返回stream的尾部(一个包含有余下所有元素的stream)，很可能是一个空的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();  
        } );  
    } );  
} );  
// the head of the t stream is 10; its tail has a head which is 20 and a tail which  
// has a head which is 30 and a tail which is the empty stream.  
t.print(); // prints 10, 20, 30

没事找事吗？直接用Stream.make( 10, 20, 30 )就可以做这个。但是，请注意，这种方式我们可以轻松的构建我们的无穷大stream。让我们来做一个能够无穷无尽的stream：

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 the function ones() (this same function!)  
        ones  
    );  
}  
   
var s = ones();      // now s contains 1, 1, 1, 1, ...  
s.take( 3 ).print(); // prints 1, 1, 1

请注意，如果你在一个无限大的stream上使用 s.print()，它会无休无止的打印下去，最终耗尽你的内存。所以，你最好在使用s.print()前先s.take( n )。在一个无穷大的stream上使用s.length()也是无意义的，所有，不要做这些操作；它会导致一个无尽的循环(试图到达一个无尽的stream的尽头)。但是对于无穷大stream，你可以使用s.map( f ) 和 s.filter( f )。然而，s.walk( f )对于无穷大stream也是不好用。所有，有些事情你要记住; 对于无穷大的stream，一定要使用s.take( n )取出有限的部分。

让我们看看能不能做一些更有趣的事情。还有一个有趣的能创建包含自然数的stream方式：

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  
            // which is 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 indeed are the REST of the natural numbers after one  
            return ones().add( naturalNumbers() );  
        }   
    );  
}  
naturalNumbers().take( 5 ).print(); // prints 1, 2, 3, 4, 5

细心的读者会发现为什么新构造的stream的第二参数是一个返回尾部的函数、而不是尾部本身的原因了。这种方式可以通过延迟尾部截取的操作来防止进行进入无穷尽的执行周期。

让我们来看一个更复杂的例子。下面的是给读者留下的一个练习，请指出下面这段代码是做什么的？

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的头元素是什么。然后找出第二个元素是什么(余下的元素的头元素)；然后第三个元素，然后第四个。这个函数的名称也能给你一些提示。如果你对这种难题感兴趣，这儿还有一些：

var sequence = new Stream( 1, function() {
    return new Stream( 1, function() {
        return sequence.add( sequence.tail() );
    } );
} ); 
 
sequence.take( 10 ).print();

如果你真的想不出这段代码是做什么的，你就运行一下它，自己看一看！这样你就很容易理解它是怎么做的了。

致敬

Streams 实际上不是一个新的想法。很多的函数式的编程语言都支持这种特征。所谓‘stream’是Scheme语言里的叫法，Scheme是LISP语言的一种方言。Haskell语言也支持无限大列表(list)。这些'take', 'tail', 'head', 'map' 和 'filter' 名字都来自于Haskell语言。Python和其它很多中语言中也存在虽然不同但很相似的这种概念，它们都被称作"发生器(generators)"。

这些思想来函数式编程社区里已经流传了很久了。然而，对于大多数的Javascript程序员来说却是一个很新的概念，特别是那些没有函数式编程经验的人。这里很多的例子和创意都是来自Structure and Interpretation of Computer Programs这本数。如果你喜欢这些想法，我高度推荐你读一读它；这本书可以在网上免费获得。它也是我开发这个Javascript类库的创意来源。

如果你喜欢其它语法形式的stream，你可以试一下linq.js，或者，如果你使用 node.js， node-lazy 也许更适合你。如果你要是喜欢 CoffeeScript 的话， Michael Blume 正在把 stream.js 移植到 CoffeeScript 上，创造出 coffeestream。