新しい JavaScript データ構造 Streams

最近、インターネット上で新しい Javascript アプレット - Streams を見ました。最初は普通の Javascript クラス ライブラリだと思いましたが、それについての紹介を読んだ後、これは単純なクラス ライブラリではなく、作者の焦点であることがわかりました。このクラス ライブラリの機能ではありませんが、記事から一節を引用すると、この記事を 10 分でも読んでいただければ、プログラミングの理解が完全に変わるかもしれません (機能的なプログラミングの経験がない限り!)。

また: ストリームは実際には新しいアイデアではありません。多くの関数型プログラミング言語がこの機能をサポートしています。いわゆる「ストリーム」は Scheme 言語での名前であり、Scheme は LISP 言語の方言です。 Haskell 言語は、無限大のリストもサポートしています。 「take」、「tail」、「head」、「map」、「filter」という名前はすべて Haskell 言語に由来しています。この異なるものの似た概念は Python や他の多くの中国語にも存在し、それらはすべて「ジェネレーター」と呼ばれます。これらのアイデアは、関数型プログラミング コミュニティで長い間広まっていました。ただし、ほとんどの JavaScript プログラマ、特に関数型プログラミングの経験のないプログラマにとって、これは非常に新しい概念です。

stream.js

stream.js は、新しい Javascript データ構造である streams.

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

を提供する、小規模で完全に独立した Javascript ライブラリ (わずか 2k) です。ストリームは、配列やリンク リストによく似た操作が簡単なデータ構造ですが、いくつかの優れた機能が追加されています。

彼らの何がそんなに特別なのでしょうか？配列とは異なり、ストリームは魔法のようなデータ構造です。無限の数の要素を保持できます。はい、正しく聞こえました。彼の魔法は、怠惰に実行する能力から来ています。この単純な用語は、無限の数の要素をロードできることを完全に意味します。

ストリームをダウンロード

入門

この記事を 10 分でも読んでいただければ、プログラミングの理解が完全に変わるかもしれません (関数型プログラミングの経験がない場合は除く)。しばらくお待ちください。まず、配列またはリンク リストによく似たストリームによってサポートされる基本的な関数操作を紹介します。次に、その非常に興味深い機能をいくつか紹介します。

ストリームはコンテナです。要素を保持しています。 Stream.make を使用すると、ストリームにいくつかの要素をロードさせることができます。必要な要素をパラメータとして渡すだけです:

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

非常に単純ですが、s は 3 つの要素 (10、20、および 30) を順番に含むストリームです。 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

new Stream() を使用するか、Stream.make() を直接使用して空のストリームを構築することもできます。 s.tail() メソッドを使用すると、最初の要素を除くストリーム内の残りの要素をすべて取得できます。空のストリームで s.head() メソッドまたは s.tail() メソッドを呼び出すと、例外がスローされます。ストリームが空かどうかは、true または false を返す 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() は、ストリーム内のすべての要素を出力します。

他に何ができるでしょうか?

もう 1 つの便利な関数は、Stream.range( min, max ) 関数です。最小値から最大値までの自然数を含むストリームを返します。

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

このストリームでは、地図、フィルター、ウォークなどの機能を使用できます。 s.map( f ) は関数であるパラメータ f を受け取ります。ストリーム内のすべての要素は f によって処理され、その戻り値はこの関数によって処理されたストリームです。たとえば、これを使用してストリーム内の数値を 2 倍にすることができます:

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 を受け入れます。ストリーム内のすべての要素はこの関数によって処理されますが、戻り値には f 関数が返すことを許可する要素のみが含まれます。真実。 。したがって、これを使用して、ストリーム内の特定の要素をフィルター処理できます。このメソッドを使用して、前のストリームに基づいて奇数のみを含む新しいストリームを構築しましょう:

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。