JavaScript实现yield

一.问题重述

迭代器是一种用来简化遍历操作的对象,从最基本的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,笔者添上了yieldyieldSeq

优雅的递归方案,但出题人(Jeffrey Zhao)承认,ivony的方案(解法1)更适合js

五.总结

  • yield实现方式都采用了函数注入的方式,即先声明参数,在最终执行context中再提供函数具体实现

  • 闭包保留context,在处理无限集时非常好用

  • 递归方案总是很简洁,问题是,要么想不到,要么想不通。。

一点废话:老司机们内力深厚,无论是健壮性(e !== exception)、实用性(数组方案)还是优雅程度(花式yield)都没的说。如温前辈所说的,社区是个很好的学习途径,看别人代码能够更快地提高自我

测试文件:http://www.ayqy.net/temp/yield.html

参考资料

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code