一.问题重述
迭代器是一种用来简化遍历操作的对象,从最基本的value
, next()
接口到each()
, take()
, select()
, takeWhile()
等高级接口,都是进一步简化遍历操作的
手动实现迭代器很麻烦,需要维护内部状态,而且语法也不够优雅,可读性就更不用说了,例如:
function Iterator123(value) {
this._value = value;
this.value = this._value;
}
Iterator123.prototype.next = function() {
if (this._value >= 3) {
return false;
}
else {
return new Iterator123(this.value+1);
}
}
function oneToThree() {
return new Iterator123(1);
}
// use
for (var iter = oneToThree(); iter; iter = iter.next()) {
log(iter.value);
}
C#提供了yield关键字快速生成迭代器,能够生成迭代器的东西叫迭代器的生成器(简称生成器),例如C#语法:
public static IEnumerable<int> OneToThree()
{
yield return 1;
yield return 2;
yield return 3;
}
调用OneToThree()
生成迭代器后,就可以MoveNext()
了,创建迭代器的语法非常优雅(yield return
)
问题:用js实现类似的yield生成器
P.S.问题来自趣味编程:在JavaScript中实现简单的yield功能(问题)
二.解法1(from ivony)
代码自己会说话:
log('from ivony');
function YieldHost(yieldFunction) {
this._yieldFunction = yieldFunction;
}
YieldHost.prototype.each = function(processor) {
var yield = function (result) {
processor(result);
};
this._yieldFunction(yield);
}
// use
function fun1(yield)
{
yield(1);
yield(2);
yield(3);
}
function fun2(yield) {
for (var i = 0; i < 3; i++)
yield(i);
}
// 传入yieldFun,返回匿名函数,接受processor
// 匿名函数内部实现了yield函数
var iter1 = new YieldHost(fun1);
var iter2 = new YieldHost(fun2);
// 传入processor,用来处理yield返回结果
// 此处只是简单输出
iter1.each( function(item) {
log(item);
});
iter2.each( function(item) {
log(item);
});
(代码来自ivony,笔者修改了代码结构,使之更像js)
思路:先根据传入的processor组装出yield方法,再执行含有yield调用的yieldFun
特点:实现了易用的生成器,结构通用,但顺序执行,停不下来
前辈很快给出了能停下来的办法(没错,就是throw...catch
),代码如下:
log('from ivony');
function YieldHost(yieldFunction) {
this._yieldFunction = yieldFunction;
}
YieldHost.prototype.eachCanBreak = function(processor) {
var exception = Math.random();
var yield = function(result) {
processor(result);
}
try {
this._yieldFunction(function (result) {
if (processor(result))
throw exception;
});
}
catch (e) {
// 防止掩盖其它异常
if (e !== exception)
throw e;
}
};
YieldHost.prototype.take = function(size) {
var that = this;
return function (fun) {
that.eachCanBreak(function (item) {
if (size-- == 0)
return true;
else
return fun(item);
});
}
};
YieldHost.prototype.select = function(selector) {
var that = this;
return function (fun) {
that.eachCanBreak(function (item) {
return fun(selector(item));
});
}
};
function fun1(yield) {
for (var i = 0; i < 5; i++) {
yield(i);
}
}
function fun2(yield) {
var i = 0;
while (true)
yield(i++);
}
// 遍历有限集,条件中断
var iter1 = new YieldHost(fun1);
iter1.eachCanBreak(function(item) {
if (item > 1) {
return true;
}
log(item);
});
// 遍历无限集
var iter2 = new YieldHost(fun2);
iter2.take(3)(function(item) {
log(item);
});
// select
iter1.select(function(item) {
return item * 2;
})(function(item) {
log(item);
});
(代码来自ivony,笔者修改了代码结构,使之更像js)
用异常实现中断,可以停下来了,但无法实现next(因为从一开始就放弃了next,只实现each,从实用的角度来说没什么问题),原文解释了设计思路:
yieldHost就是完成了一个倒装的工作,把enumerator接收的那个函数(也就是window.alert( item ),注到了枚举函数中(即fun)
把处理函数processor注入到迭代函数fun中,注入的形式把processor包装成yield
三.解法2(from Dexter.Yy)
会说话的代码如下:
log('from Dexter.Yy');
function generator(fn, args){
var queue, cache = [];
// 给参数列表末尾添上yield
args.push(yield);
// 填充结果数组cache
fn.apply(this, args);
// 逆置cache,便于pop实现next
init();
return {
next: next,
close: init,
each: function(fn, context){
var result, i = 0;
// 防止中途调用,导致不完全遍历
this.close();
while (result = this.next()) {
fn.call(context || window, result, i++);
}
}
};
// 装入数据
function yield(result){
cache.push(result);
}
// 取出数据
function next(){
return queue.pop();
}
function init(){
queue = cache.slice().reverse();
}
};
// 最后一个参数必须是yield
function foo(a, b, yield){
for (var i = 0; i <= 10; i++)
yield(a + b + i);
}
var iter = generator(foo, [1, 2]);
log(iter.next());
log(iter.next());
log(iter.next());
iter.close();
log(iter.next());
iter.each(function(item, i){
log('i = ' + i + ', item = ' + item);
});
(代码来自Dexter.Yy,笔者添加了注释)
特点:简单易用的生成器,虽然是数组实现的,不支持无限集,但很实用
前辈也给出了支持无限集的方式:
log('from Dexter.Yy');
// 避免一开始就对整个序列求值
function generator(fn, args){
var routine, self = this;
// 在参数列表末尾添上yield
args.push(yield);
//
init();
return {
next: next,
close: init
};
function yield(result){
return result;
}
function next(){
// 不需要像原版这样写
// return routine.apply(self, arguments);
return routine();
}
function init(){
routine = fn.apply(self, args);
}
}
// 最后一个参数必须是yield
function fibonacci(n, yield) {
var n1 = n2 = s = i = 1;
// 闭包保留context,以实现next
return function(){
for(; i<n; i++){
s = n1 + n2;
n1 = n2;
n2 = s;
return yield(n1);
}
};
}
var fibIter = generator(fibonacci, [1000]);
log(fibIter.next());
log(fibIter.next());
fibIter.close();
log(fibIter.next());
log(fibIter.next());
log(fibIter.next());
很容易发现,其实并不需要yield
,支持无限集其实是取决于fib
的实现,与生成器没什么关系,不用生成器、迭代器更简洁,例如:
function fib(n) {
var n1 = n2 = s = i = 1;
// 闭包保留context,以实现next
return function(){
for(; i<n; i++){
s = n1 + n2;
n1 = n2;
n2 = s;
return n1;
}
};
}
var max = 1000;
var fun = fib(max);
log(fun());
log(fun());
log(fun());
log(fun());
四.解法3(from Jeffrey Zhao)
出题人准备的标准答案:
log('from Jeffrey Zhao');
function oneToThree() {
return yield(1, function () {
return yield(2, function () {
return yield(3);
});
});
}
function numSeq(n) {
return yield(n, function () {
return yieldSeq(numSeq(n + 1));
});
}
function range(minInclusive, maxExclusive) {
if (minInclusive >= maxExclusive) return null;
return yield(minInclusive, function () {
return yieldSeq(range(minInclusive + 1, maxExclusive));
});
}
function fibSeq() {
function fibSeq$(a, b) {
var next = a + b;
return yield(next, function () {
return yieldSeq(fibSeq$(b, next));
});
}
return yield(0, function () {
return yield(1, function () {
return yieldSeq(fibSeq$(0, 1));
});
});
}
function yield(item, fn) {
return {
value: item,
next: function() {
if (typeof fn === 'function') {
return fn();
}
else {
return false;
}
}
};
}
function yieldSeq(iter) {
if (iter) {
return {
value: iter.value,
next: function() {
return iter.next();
}
};
}
else {
return false;
}
}
// use
for (var iter = oneToThree(); iter; iter = iter.next()) {
log(iter.value);
}
for (var iter = range(0, 3); iter; iter = iter.next()) {
log(iter.value);
}
for (var iter = numSeq(0); iter; iter = iter.next()) {
if (iter.value > 2) {
break;
}
log(iter.value);
}
for (var iter = fibSeq(); iter; iter = iter.next()) {
if (iter.value > 10) {
break;
}
log(iter.value);
}
(部分代码来自Jeffrey Zhao,笔者添上了yield
和yieldSeq
)
优雅的递归方案,但出题人(Jeffrey Zhao)承认,ivony的方案(解法1)更适合js
五.总结
yield
实现方式都采用了函数注入的方式,即先声明参数,在最终执行context中再提供函数具体实现闭包保留context,在处理无限集时非常好用
递归方案总是很简洁,问题是,要么想不到,要么想不通。。
一点废话:老司机们内力深厚,无论是健壮性(e !== exception
)、实用性(数组方案)还是优雅程度(花式yield)都没的说。如温前辈所说的,社区是个很好的学习途径,看别人代码能够更快地提高自我
测试文件:http://www.ayqy.net/temp/yield.html