跳到主要內容
黯羽輕揚每天積累一點點

JavaScript 實現 yield

免費2015-10-25#JS#JavaScript的yield#js的yield#js yield#js yield return#JavaScript迭代器#JavaScript生成器#js迭代器#js生成器

5 年前前輩們就在討論怎麼優雅地實現 js 的生成器，雖然現在 es6 已經給了，但想想前輩們的實現要比去看 API 用法有趣得多

一。問題重述

迭代器是一種用來簡化遍歷操作的對象，從最基本的 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

參考資料

評論

暫無評論，快來發表你的看法吧

提交評論