I. Problem Restatement
Iterator is an object used to simplify traversal operations. From basic value, next() interfaces to advanced interfaces like each(), take(), select(), takeWhile(), all further simplify traversal operations.
Manually implementing an iterator is troublesome, requiring maintenance of internal state, and the syntax is not elegant enough, not to mention readability. For example:
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# provides the yield keyword to quickly generate iterators. Something that can generate iterators is called an iterator generator (简称 generator). For example, C# syntax:
public static IEnumerable<int> OneToThree()
{
yield return 1;
yield return 2;
yield return 3;
}
After calling OneToThree() to generate an iterator, you can MoveNext(). The syntax for creating iterators is very elegant (yield return).
Problem: Implement a similar yield generator in JS.
P.S. Problem from Fun Programming: Implementing Simple yield Functionality in JavaScript (Problem)
II. Solution 1 (from ivony)
The code speaks for itself:
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);
});
(Code from ivony, author modified code structure to make it more like JS)
Idea: First assemble the yield method based on the passed-in processor, then execute the yieldFun containing yield calls.
Features: Implemented a usable generator, general structure, but sequential execution, cannot stop.
Seniors quickly provided a way to stop (yes, it's throw...catch). Code as follows:
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);
});
(Code from ivony, author modified code structure to make it more like JS)
Using exceptions to implement interruption, it can stop now, but cannot implement next (because gave up on next from the start, only implemented each, from a practical perspective there's no problem). The original text explained the design idea:
yieldHost just completed an inversion work, injecting the function that enumerator receives (that is window.alert( item ), noted into the enumeration function (i.e. fun)
Injecting the processing function processor into the iteration function fun, the form of injection wraps processor into yield.
III. Solution 2 (from Dexter.Yy)
The code that speaks for itself is as follows:
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);
});
(Code from Dexter.Yy, author added comments)
Features: Simple and usable generator, although implemented with arrays, does not support infinite sets, but very practical.
Seniors also provided a way to support infinite sets:
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());
It is easy to discover that actually yield is not needed. Supporting infinite sets actually depends on the implementation of fib, has nothing to do with the generator. Without generator, iterator, it is more concise. For example:
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());
IV. Solution 3 (from Jeffrey Zhao)
Standard answer prepared by the question setter:
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);
}
(Partial code from Jeffrey Zhao, author added yield and yieldSeq)
Elegant recursive solution, but the question setter (Jeffrey Zhao) admitted that ivony's solution (Solution 1) is more suitable for JS.
V. Summary
-
yieldimplementation methods all adopted the function injection method, that is, declare parameters first, then provide the function concrete implementation in the final execution context. -
Closure retains context, very useful when dealing with infinite sets.
-
Recursive solutions are always concise, the problem is, either you can't think of it, or you can't understand it..
Some remarks: Veterans have deep internal strength, whether it is robustness (e !== exception), practicality (array solution) or elegance level (fancy yield) there is nothing to say. As Senior Wen said, community is a very good learning pathway, looking at others' code can improve oneself faster.
Test file: http://www.ayqy.net/temp/yield.html
No comments yet. Be the first to share your thoughts.