趣味编程：在JavaScript中实现简单的yield功能（问题）
2010-06-08 15:33 by 老赵, 8243 visits说起迭代器（Iterator）大家一定都不陌生，无论是是Java，C#或是Python等语言都有内置标准的迭代器结构，它们也都提供了内置的for或foreach关键字简化迭代器的“使用”。不过对于迭代器的“生成”，不同语言之间的就会有很大差距。例如，在C#和Python中都提供了yield来简化迭代器的“创建”，此时生成一个迭代器便再简单不过了。但对于Java程序员来说，即使到了Java 7还必须为在迭代器内部手动维护状态，非常痛苦。而更重要的一点是，利用yield我们可以轻松地创建一个“延迟”的，“无限”的序列。那么，我们能否在JavaScript中享受到这样的yield生成器呢？
yield的功效
先来演示一下yield的作用，例如我们要写一个C#方法，返回一个迭代器（即.NET中的IEnumerable），它会生成从minInclusive到maxExclusive之间的整数序列：
// C# public static IEnumerable<int> Range(int minInclusive, int maxExlusive) { for (int i = minInclusive; i < maxExlusive; i++) yield return i; }
而在Java中便会麻烦许多：
// Java public class Range implements Iterable<Integer> { private int m_maxExclusive; private int m_current; public Range(int minInclusive, int maxExclusive) { this.m_maxExclusive = maxExclusive; this.m_current = minInclusive; } @Override public Iterator<Integer> iterator() { return new Iterator<Integer>() { public boolean hasNext() { return m_current < m_maxExclusive; } public Integer next() { int current = m_current; m_current = m_current + 1; return current; } public void remove() { throw new UnsupportedOperationException(); } }; } }
其实就最终执行的代码来说，C#和Java是差不多的，只不过C#的编译器帮助开发人员节省了许多工作。事实上，在这个简单的示例中其实还不能体现出yield的优越性，您可以想象一下，如果我们迭代器中需要有更多的逻辑，如while，if，for，break等配合使用，那么yield会带来多大的可读性。嗯，就说可读性，如果给您上面编写的Range类，您多久可以理解它的作用呢？再观察一下C#代码呢？
可能您会说，完全可以在Range类中先创建一个数组，保存所有元素，然后在next()时一一返回，这可读性就强了。没错，只可惜这样做会占用太多内存。假如我传入-108和108作为参数，那程序十有八九会出现问题（顺便一问，创建这样一个数组需要占用多少内存？）。yield的一个重要特性便是“延迟”，便是“按需生成”。我们完全可以创建一个“范围”十分巨大——甚至是无限大的迭代器：
// C# public static IEnumerable<int> Infinite(int start) { while (true) yield return start++; }
然后只取其前N项使用：
// sum of 0 .. 99 int sum = Infinite(0).Take(100).Sum();
此外yield还有一些十分重要的使用模式，不过这方面话题我打算留在《Why Java Sucks and C# Rocks（6）：yield及其作用》一文中进行详细讨论了。
JavaScript中的迭代器
JavaScript中有迭代器吗？有迭代器的生成器（即yield类似功能）吗？有，还真有，您可以关注一下MDN中的JavaScript 1.7说明，其中就有几乎和C#完全一样的功能，例如这样生成并使用一个无限的斐波那契数列：
// JavaScript function fib() { var i = 0, j = 1; while (true) { yield i; var t = i; i = j; j += t; } } var g = fib(); for (var i = 0; i < 10; i++) { document.write(g.next() + "<br />"); }
只不过我们目前还没法编写这样的JavaScript代码，如果要使用迭代器，那么还得自己动手丰衣足食。
其实如果不谈“生成器”，光“迭代器”本身是没有任何神秘之处的，它们只是一种定义好的“编程模型”罢了，例如Java里的Iterable和Iterator或是.NET里的IEnumerable和IEnumerator。因此，如果要说建立一个迭代器，那么其实只是确定一个编程模型：
// JavaScript function range(minInclusive, maxExclusive) { // ... } for (var iter = range(0, 10); iter; iter = iter.next()) { document.write(iter.value + "<br />"); }
range方法会返回一个迭代器，然后可以在一个for里进行使用。您会发现这个模型和.NET或是Java里的迭代器都不一样，它们在遍历过程中使用的都是同一个迭代器，而在我的模型中，一个迭代器其实更像是一个单向链表，它包含两个成员，value字段用于表示当前的值，next方法则返回下一个节点。这么做的原因是，我比较懒的写一些包含副作用的逻辑，因为维护状态实在是一件麻烦的事情，远不如创建并返回新对象来的简单。
如果使用“创建数组”的方法来实现一个迭代器，那么range的确很简单：
// JavaScript function ArrayIterator(array, index) { this.value = array[index]; this._array = array; this._index = index; } ArrayIterator.prototype.next = function () { var newIndex = this._index + 1; if (newIndex >= this._array.length) return null; return new ArrayIterator(this._array, newIndex); } function range(minInclusive, maxExclusive) { var array = []; for (var i = minInclusive; i < maxExclusive; i++) { array.push(i); } return new ArrayIterator(array, 0); }
这段代码您一定能够理解，我就不多做解释了。这种做法的优势在于十分容易实现，但是缺点也很明显，之前已经谈过就不再重复了。
题目要求
那么，我们又能否为JavaScript添加“生成器”？我的意思是，像yield那样的生成器。要求很简单，只要能用它实现最简单的功能即可，例如：
// C# public static IEnumerable<int> OneToThree() { yield return 1; yield return 2; yield return 3; }
如果您觉得实现这个非常简单，不妨再尝试着使用更好的做法来实现刚才的range函数。此外，您也可以实现如刚才C#的Infinite那样的无限数列，或者……那著名的斐波那契数列也可以咯。这样“求出斐波那契数列中，所有N以内的元素之和”便可以简单地：
function fibSeq() { /* ... */ } function sumOfFib(max) { return toIter(fibSeq()).takeWhile(function (i) { return i <= max}).sum(); }
如何，一起来尝试一下吧！
沙发我来做。