新的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。