Hello World
Spiga

趣味编程:在JavaScript中实现简单的yield功能(问题)

2010-06-08 15:33 by 老赵, 8239 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();
}

如何,一起来尝试一下吧!

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

90 条回复

  1. KevinComo
    61.172.247.*
    链接

    KevinComo 2010-06-08 15:58:19

    沙发我来做。

  2. 老赵
    admin
    链接

    老赵 2010-06-08 16:27:08

    @KevinComo

    做题做题,好久没搞趣味编程了。

  3. JimLiu
    221.223.44.*
    链接

    JimLiu 2010-06-08 16:28:59

    yield对复杂数据结构(甚至不复杂的,就像二叉树这种)迭代器实现实在太优雅太便捷了,尤其我经常和数据结构打交道的,这是我最喜欢的C#特性之一。

  4. fw
    123.124.137.*
    链接

    fw 2010-06-08 16:49:39

    function yield(first, last) {
        if (last < first)
            return false;
    
        this.value = first;
        this.last = last;
    
        return this;
    }
    
    yield.prototype.next = function () {
        this.value += 3;
        return this.value < this.last ? this : false;
    }
    
    function range(first, last) {
        return new yield(first, last);
    }
    
    for (var iter = range(0, 10); iter; iter = iter.next()) {
        document.write(iter.value + "<br />");
    }
    

    能得几分?

  5. 链接

    clk_z 2010-06-08 16:53:03

    很想领教一下老赵那强大的JS能力,居然比C#都强,以后多搞点JS方面的东西分享啊!先谢过!

    我承认我是来学习的,老赵最后会公布答案么?热情关注!

  6. 老赵
    admin
    链接

    老赵 2010-06-08 17:06:44

    @fw

    零分,嘿嘿。

    关键是要通用啊,没那么简单的。最后题目里说了,能用来实现oneToThree,range,infinite,fib等各种序列的yield结构才好,呵呵。

  7. 老赵
    admin
    链接

    老赵 2010-06-08 17:07:39

    @clk_z

    嗯,答案已经准备好了,本来想一起发布,后来发现有点长,忽然意识到能够放进“趣味编程”,于是就先放出题目了。

    不过这里其实和JavaScript关系不大啊,其实我一直不觉得JavaScript编程有什么特别的,也就是一种普通的语言吧……

  8. infinte
    60.166.104.*
    链接

    infinte 2010-06-08 17:14:06

    这个题目我记下了,今天晚上我网站上给答案。

  9. fw
    123.124.137.*
    链接

    fw 2010-06-08 17:15:16

    哦,我看成给你那个契约换个不是数组的实现了呢

  10. 老赵
    admin
    链接

    老赵 2010-06-08 17:27:01

    @infinte

    欢迎欢迎。话说老兄的博客内容很多啊,我们交换链接如何?

  11. 老赵
    admin
    链接

    老赵 2010-06-08 17:27:29

    @fw

    没懂你意思……不过您这个题意看的的确有点偏,呵呵。

  12. infinte
    60.166.104.*
    链接

    infinte 2010-06-08 17:32:23

    @老赵:

    可以。

  13. JimLiu
    221.223.44.*
    链接

    JimLiu 2010-06-08 17:33:17

    function yield(func, scope){
        this.__scope = scope||window;
        this.value = func.apply(this.__scope);
        this.__func = func;
        return this;
    }
    yield.stop={};
    yield.prototype.next = function(){
        this.value = this.__func.apply(this.__scope);
        return this.value==yield.stop ? false : this;
    };
    
    function range(a, b){
        var i=a;
        return new yield(function(){
            if (i==b) return yield.stop;
            return i++;
        });
    }
    function fib(n){
        var i = 0, j = 1;
        return new yield(function(){
            if (n==0) return yield.stop;
            n--;
            var t = i;
            i = j;
            j += t;
            return i;
        });
    }
    
    for(var it=fib(10); it; it=it.next()){
        document.write(it.value + '<br />');
    }
    

    没能实现

    // C#
    public static IEnumerable<int> OneToThree()
    {
        yield return 1;
        yield return 2;
        yield return 3;
    }
    
  14. 老赵
    admin
    链接

    老赵 2010-06-08 17:55:18

    @JimLiu

    好像这编程体验不太好呢,呵呵,最好可以yield...yield...yield之类的,就像你给的这段C#一样。否则其实还是和Java差不多,需要自己维护状态之类的。

  15. infinte
    60.166.104.*
    链接

    infinte 2010-06-08 17:56:06

    答案已给。自己看这里

  16. 链接

    Jim Liu 2010-06-08 17:59:37

    @老赵

    编程体验的确有点恼人,主要还是考虑到闭包,C#里的yield“闭包”已经被编译器包办,整合到了语法层面上。

    我再寻思下……

  17. 老赵
    admin
    链接

    老赵 2010-06-08 18:14:37

    @infinte

    话说你这好像不是延迟的,按需生成,不能用来生成无限的序列哎。

  18. infinte
    60.166.104.*
    链接

    infinte 2010-06-08 18:19:02

    @老赵:

    JavaScript没有提供类似Ruby的协同例程之类的东西,无法进行“非常精确”的流程控制。 除非手工编自动机或者写解释器否则几乎不可能完成延迟。

  19. 老赵
    admin
    链接

    老赵 2010-06-08 18:22:53

    @infinte

    是的,所以要换种思路。我的方法虽然结果不是很好看限制其实也很多,但是很简单,思路也很有趣,感觉在其他方面也有参考意义,呵呵。

    总的来说,就先解决oneToThree,range和fib三个方法吧。

  20. 链接

    miloyip 2010-06-08 18:44:58

    沒信心這是否乎合要求啊,return this.yeild(x) 一定要放到循環的最後,但好像算是挺簡單的做法:

    iterator = {
        yield : function(x) {
            this.value = x;
            return this;
        }
    };
    
    function OneToThree() {
        this.__proto__ = iterator;
    
        this.next = function() {
            switch(this.value) {
                case undefined: return this.yield(1);
                case 1: return this.yield(2);
                case 2: return this.yield(3);
            }
            return null;
        };
    
        return this.next();
    }
    
    
    function Range(minInclusive, maxExclusive) {
        this.__proto__ = iterator;
    
        var i = minInclusive;
        this.next = function() {
            for (; i < maxExclusive; ) // 此句可改成if,這悝只是想變得更像原來的C#代碼
                return this.yield(i++);
            return null;
        };
    
        return this.next();
    }
    
    function Infinite(start) {
        this.__proto__ = iterator;
    
        this.next = function() {
            while (true) // 此句可有可無,只是想變得更像原來的C#代碼
                return this.yield(start++);
        };
    
        return this.next();
    }
    
    function Fib() {
        this.__proto__ = iterator;
    
        var i = 0, j = 1;    
        this.next = function() {
            while (true) {  // 此句可有可無,只是想變得更像原來的C#代碼
                var t = i;
                i = j;
                j += t;
                return this.yield(t);
            }
        }
    
        return this.next();
    }
    
    document.write("OneToThree()<br/>");
    for (var iter = OneToThree(); iter; iter = iter.next())
        document.write(iter.value + "<br/>");    
    
    document.write("Range(0, 10)<br/>");
    for (var iter = Range(0, 10); iter; iter = iter.next())
        document.write(iter.value + "<br/>");    
    
    document.write("Infinite(5)<br/>");
    var inf = Infinite(5);
    for (var i = 0; i < 10; i++, inf = inf.next())
        document.write(inf.value + "<br/>");
    
    document.write("Fib()<br/>");
    var fib = Fib();
    for (var i = 0; i < 10; i++, fib = fib.next())
        document.write(fib.value + "<br/>");
    
  21. 链接

    陈梓瀚(vczh) 2010-06-08 19:23:36

    moliyip的做法就是yield return的展开版……老赵的要求还是比较苛刻啊,我也不知道他究竟想要什么。如果想要100%模仿,那么必须在yield return的时候将函数暂停,运行权利交还给外面,等到在需要一个东西的时候,外面暂停,运行权利交给运行了一半的yield函数。

    这让我想起了小时候给ARPG开发脚本引擎,因为ARPG的脚本需要一个MessageBox来显示主角的对话,这个时候脚本暂停,等到游戏按下了enter,鼠标还是其他什么鬼东西的时候,脚本才继续运行。这就类似cin>>,或者是Console.ReadLine(),函数在这个时候已经暂停了,而流程则交由另一个程序运行一直到他们的任务继续不下去了需要函数再提供一些信息为止。

    那么就有问题了。我很少见到有什么不lazy evaluated的程序是支持这种执行流程的。所以C#才会将有yield函数里面的上下文统统保存在一个类的成员变量里面,然后每一个yield return都拥有一个状态,最后大概是用一个大型的switch来实现,就如同moliyip所做的。

    结论:我不知道老赵想模仿到什么程度,反正跟C#一样【把所有的中间状态都做在一个函数里,然后返回值还是一个迭代器】,javascript是不行的。

  22. infinte
    60.166.104.*
    链接

    infinte 2010-06-08 19:23:53

    @老赵

    我的Emitter可能更接近Ruby的迭代器,我补充了一个takeWhile的实现。不同的思路。

  23. 链接

    陈梓瀚(vczh) 2010-06-08 19:35:11

    不过换一种思路来说,haskell在做lazy list的时候,返回值一直都是first_value : tail_list。我在想,如果我们总是在javascript的程序里面返回(我不懂语法,模仿C#)pair(first_value, () => tail_list)的话,在外面套上一个迭代器是十分好写的。但是这已经不是yield return。

    function oneTwoThree()
    {
        return [1, [()=>[2, ()=[3, ()=>[]]]];
    }
    
    function range2(now, end)
    {
      return now==end?[] : [now, ()=>range2(now+1, last)];
    }
    
    function range(first, count)
    {
        return range2(first, first+count)
    }
    
    function fib2(first, second, index, count)
    {
        return index==count?[]:[first+second, ()=>fib2(second, first+second, index+1, count)];
    }
    
    function list_of_fib_numbers(count)
    {
        if(count==1)return [1,()=>[]];
        else if (count==2) return [1,()=>[1, ()=>[]]];
        else return fib2(1, 1, 0, count-2);
    }
    
    // 再次声明我不会javascript语法,反正我要写一个迭代器的类
    class iterator
    {
        var lazy_expression;
    
        function available()
        {
            return lazy_expression is not an empty array;
        }
    
        function current()
        {
            return lazy_expression[0];
        }
    
        function next()
        {
            lazy_expression = lazy_expression[1];
            return available();
        }
    }
    
    function build_iterator(e)
    {
        return new iterator{lazy_expression = e;}
    }
    
  24. 链接

    陈梓瀚(vczh) 2010-06-08 19:36:19

    能不能给我一个勾,让我选择不想用那些破文字的效果转换文法啊,你让user惊讶了,是user experience的bug。

  25. ArieShout
    64.233.172.*
    链接

    ArieShout 2010-06-08 19:44:01

    迭代器的状态不是应该由迭代器本身来维护的么?为啥用容器类的成员来维护了

    拿老赵的Java Range的例子说,

    Range r = new Range(0, 10);
    int count = 0;
    for (int i : r) {
        System.out.print(i);
        if (++count == 5)
            break;
    }
    System.out.print("#");
    for (int i : r) {
        System.out.print(i);
    }
    

    =>

    01234#56789

  26. 链接

    miloyip 2010-06-08 20:01:48

    @陈梓瀚(vczh): 那么就有问题了。我很少见到有什么不lazy evaluated的程序是支持这种执行流程的。所以C#才会将有yield函数里面的上下文统统保存在一个类的成员变量里面,然后每一个yield return都拥有一个状态,最后大概是用一个大型的switch来实现,就如同moliyip所做的。

    其實很多語言也支持Coroutine功能,例如我喜愛的Lua。

    P.S. 我的名字是 Milo Yip……,不是moli或loli……

  27. vczh
    222.64.226.*
    链接

    vczh 2010-06-08 20:25:55

    主页出错登陆不鸟了……其实lazy+monad的语言都可以看成是有内置的coroutine……

  28. infinte
    60.166.104.*
    链接

    infinte 2010-06-08 20:32:07

    @miloyip

    Loli……哈哈哈哈哈……

    其实要做loli……不对是milo的方法是没问题的,但是就美感而言……

  29. zizon
    219.136.204.*
    链接

    zizon 2010-06-08 21:01:02

    想想,其实用javascript的this特性,似乎理论上也能做一些类似寄存器/堆栈/快照之类的什么东西.?

  30. eylas
    122.194.216.*
    链接

    eylas 2010-06-08 21:07:28

    不讲效率的话

    function OneTwoThree() {
    
        var iter = {}
    
        iter.args = arguments;
        iter.hits = 0;
        iter.skip = 0;
    
        iter.body = function () {
            if(this.yield()) return 1;
            if(this.yield()) return 2;
            if(this.yield()) return 3;
            this.terminated = true;
        }
    
        iter.next = function () {
            if(this.terminated) throw {};
            this.hits += 1;
            this.skip = this.hits;
            return this.body();
        }
    
        iter.yield = function () {
            this.skip--;
            return 0==this.skip;
        }
    
        return iter;
    
    }
    
  31. 链接

    装配脑袋 2010-06-08 21:12:44

    老赵你的RSS第一次同步怎么会把所有条目都归到同一天呢。。>_<

  32. lauyee
    124.114.175.*
    链接

    lauyee 2010-06-08 21:19:55

    我的hack都没了,右侧已经乱掉了。

    我想问一下,hack是个什么东西?

  33. 老赵
    admin
    链接

    老赵 2010-06-08 21:26:38

    @陈梓瀚(vczh): 我不知道老赵想模仿到什么程度,反正跟C#一样【把所有的中间状态都做在一个函数里,然后返回值还是一个迭代器】,javascript是不行的。

    大家集思广益,不要受限在我的想法上啦。其实我的做法就是类似monad的,当然在JavaScript里实现是很丑的,唉。

  34. 老赵
    admin
    链接

    老赵 2010-06-08 21:27:16

    @装配脑袋

    我的RSS的确有bug,唉,等我空下来修改一下啊……

  35. 老赵
    admin
    链接

    老赵 2010-06-08 21:29:21

    @ArieShout: 迭代器的状态不是应该由迭代器本身来维护的么?为啥用容器类的成员来维护了

    其实我的想法本身就是:不要费脑子去维护状态,或者说是无副作用的,状态用过就抛。

  36. 老赵
    admin
    链接

    老赵 2010-06-08 21:32:39

    @lauyee

    hack就是指一些小技巧,小窍门,小补丁等非正规的手段,一般不提倡,除非作某些事情时没其他办法了。

  37. 链接

    Ivony 2010-06-08 21:36:36

    我倒是觉得JavaScript这种语言没什么不可能的呃。。。。把一个函数停住似乎不是不可能。。。

    玩得过火点还能利用解释执行的那啥么。

    事实上我觉得就是写成C#这样也完全可能哈,即使是语法错误!因为解释执行,语法错误可以绕过去。

  38. 老赵
    admin
    链接

    老赵 2010-06-08 21:37:39

    @陈梓瀚(vczh): 能不能给我一个勾,让我选择不想用那些破文字的效果转换文法啊,你让user惊讶了,是user experience的bug。

    这个很难啊……忍耐一下吧,需要发大段这种东西的情况不多的……我的目的就是让发评论稍微困难点,这样可以少灌点水,也更灵活更美观。

  39. 老赵
    admin
    链接

    老赵 2010-06-08 21:59:53

    @Ivony: 玩得过火点还能利用解释执行的那啥么。事实上我觉得就是写成C#这样也完全可能哈,即使是语法错误!因为解释执行,语法错误可以绕过去。

    这话还真没错……

  40. 链接

    Ivony 2010-06-08 22:13:13

    我在想,反过来可能好实现一些。。。。

    如果抛弃next函数,而换成each,则可能可以用一个比较小的难度得到更好的实用价值。

    enumerable.each( function( item )
    {
      //...
    } );
    
  41. 链接

    Ivony 2010-06-08 22:34:03

    按照上面的思路非常简单就实现了!代码超简洁,而且实用性也非常强。

  42. 老赵
    admin
    链接

    老赵 2010-06-08 22:39:13

    @Ivony

    你的意思是不是传入一个func作为回调或者visitor,然后在遍历时把每个节点传进去?不过这好像更像是push模型,普通的iterator都是pull模型的……

    还有,用你这个方法可以生成延迟的无限的序列吗?好像也不容易使用skip,take,takeWhile之类的进行组合的样子……

  43. 链接

    Ivony 2010-06-08 22:42:21

    超简洁实现:

    function yieldHost(yieldFunction)
    {
        return function (processer)
        {
            var yield = function (result)
            {
                processer(result);
            };
    
            yieldFunction(yield);
        };
    }
    

    怎么用?

    首先我们需要一个实现枚举的函数,它需要接受一个参数,这个参数是个函数,用于返回枚举值,像这样:

    function fun(yield)
    {
        for (var i = 0; i < 100; i++)
            yield(i);
    }
    

    拿老赵例子来说:

    function fun(yield)
    {
        yield(1);
        yield(2);
        yield(3);
    }
    

    然后利用这个yieldHost转化成为一个枚举器:

    var enumerator = yieldHost(fun);
    

    然后就可以枚举了:

    enumerator( function( item ) 
    {
        window.alert( item );
    });
    
  44. 链接

    Ivony 2010-06-08 22:46:54

    如果想要实现无穷序列,那势必要引入这样的语法了:

    enumerator( function( item )   
    {  
        window.alert( item );  
    
        if( item > 1000 )
            this.breakEnum();
    });
    

    或者像jQuery一样,return true表示break;

  45. 链接

    Ivony 2010-06-08 22:50:51

    实现了continue和break,在这个基础上再实现什么Skip、TakeWhile、Where什么的,就不在话下了。

  46. vczh
    58.38.56.*
    链接

    vczh 2010-06-08 22:51:07

    state monad什么的,就是我上面那个了……

  47. vczh
    58.38.56.*
    链接

    vczh 2010-06-08 22:58:33

    但是我仍然想知道,Take和Infinite如何分开实现,还有你是如何能把Select和Where拼在一起的,【使用】的代码要怎么写?

  48. vczh
    58.38.56.*
    链接

    vczh 2010-06-08 22:59:05

    上面To Ivony

  49. 链接

    Ivony 2010-06-08 23:05:00

    好吧,用异常对break和continue进行了不完美的实现。

    function yieldHost(yieldFunction)
    {
        var exception = Math.random();
    
        return function (processer)
        {
            try
            {
                yieldFunction(function (result)
                {
                    if (processer(result))
                        throw exception;
                });
            }
            catch (e)
            {
                if (e !== exception)
                    throw e;
            }
        };
    }
    

    To vczh,Select的参考实现:

    function Select( enumerator, selector )
    {
        return function( fun )
        {
            enumerator( function( item )
            {
                return fun( selector( item ) );
            });
        }
    }
    

    没有什么难度啊。

    至于连写?这对JavaScript好像真不是个事儿。

  50. 老赵
    admin
    链接

    老赵 2010-06-08 23:19:55

    @Ivony

    你的做法还没咋看懂,有机会好好看看。

    PS:其实兄弟们登录后就可以修改评论了不用发许多回复……

  51. 链接

    miloyip 2010-06-08 23:35:52

    我看到@Ivony的"解譯"二字,令我想到可以使用同一個iterator框架,作一個OneToThree的"解",完全是原文例子裡的C#語法。很暴力的喔 :)

    iterator = {
        yield: function(x) {
            this.value = x;
            return this;
        }
    };
    
    function sequence(text) {
        this.__proto__ = iterator;
        var regex = /\s*yield\s+return([^;]*)\s*;/g;
        this.next = function() {
            var match = regex.exec(text);
            return match == null ? null : this.yield(eval(match[1]));
        };
        return this.next();
    }
    
    function OneToThree() {
        return new sequence("\
            yield return 1;\
            yield return 2;\
            yield return 3;\
        ");
    }
    
    for (var iter = OneToThree(); iter; iter = iter.next())
        document.write(iter.value + "<br/>");
    
  52. 老赵
    admin
    链接

    老赵 2010-06-08 23:42:08

    @Ivony: 其实就是,把foreach里面的内容,注到了yield里面。。。。yield( i ) = function( item ){ window.alert( item ); }

    这个可以理解,所以我说是push模型嘛,是让迭代器把元素“推”到一个函数中去;传统的迭代器是用pull模型的,外部代码去迭代器里“拉”数据。

    不过我还是在想如何使用select,where,take,skip等做组合。可能是做得到的吧,毕竟reactive programming便是种push模型,也可以组合。不过rfx的场景多是异步的,所以我还得好好看看代码。

  53. 老赵
    admin
    链接

    老赵 2010-06-08 23:43:05

    @miloyip

    只要用类似这样的办法,那么JS的黑魔法是无穷无尽滴,嘿嘿。

  54. 老赵
    admin
    链接

    老赵 2010-06-08 23:48:58

    @Ivony

    看懂你的代码了,用异常做break很好玩。的确也可以做where,filter等东西的组合,不过组合的不是迭代器,而是访问函数了,这个方式挺有趣,不过好像已经不是迭代器的思维了(说到底还是push和pull的差别)。

    这方面似乎不如monad来的精妙啊。话说用monad其实不光是迭代器,对其它方面其实也很有启发。只可惜在JavaScript里实现monad很不好看……要说起来你的做法更适合JavaScript,且对于迭代器的场景来说更灵活。

  55. 老赵
    admin
    链接

    老赵 2010-06-08 23:59:41

    @vczh: 但是我仍然想知道,Take和Infinite如何分开实现,还有你是如何能把Select和Where拼在一起的,【使用】的代码要怎么写?

    简单的说,传统的迭代器是pull模型,我们不断进行select,where,take等组合时,其实是在不断产生新的迭代器:

    var iter = fibSeq();
    var iter_take50 = iter.take(50);
    var iter_take50_toStr = iter_take50.select(function (item) { return item.toString(); });
    
    // 接下去使用iter_take50_toStr,因此说组合的是迭代器。
    var visit = function (item) { alert(item); };
    iter_take50_toStr.forEach(visit);
    

    而@Ivony的做法是push模型,事实上组合的是访问函数。当然,编程模型也完全可以设计的和上面是十分接近的,我现在只是想表达地更清晰一些:

    var visit = function(item) { alert(item); };
    var visit_onlyFirst50 = visit.take(50);
    var visit_onlyFirst50_toStr = visit_onlyFirst50.select(...);
    
    // 然后再让一个访问函数去“遍历”这个迭代器里的元素
    var iter = fibSeq();
    iter.accept(visit_onlyFirst50_toStr);
    

    所以其实@Ivony的做法的思路是有所不同的,某些情况下的写法也会有不同,例如要做个sum,那么就是在visit里累加一个值,然后在最后读取出来──至少要让visit函数返回一个值,然后从accept方法里返回出来。

    事实上,@Ivony的做法其实就是个很典型的Reactive Programming……

  56. 老赵
    admin
    链接

    老赵 2010-06-09 00:07:08

    大家的解法都很好很强大啊,先打声招呼,我打算除了给出自己的方法外,也会再写一篇解释一下各位的做法……

  57. 链接

    miloyip 2010-06-09 00:28:35

    看完 @Ivony 的,覺得我的嘗試很低級啊。

  58. 链接

    Ivony 2010-06-09 00:41:10

    困了,脑子有点乱了,所以代码也有点乱,贴代码的时候总是要手动做一些版本还原(现在在IDE里面的代码都是调试代码)。但是这个手动的版本还原好像老出错(果然没源代码管理工具强大),修改了好几个小Bug了。先睡了,明天再来统一调试这些脚本。

  59. infinte
    60.166.104.*
    链接

    infinte 2010-06-09 00:44:58

    @老赵:

    你最好做个颁奖仪式,最好看奖、最牛叉奖…………

    另外,用异常来做break的始作俑者好像是我吧……

  60. 链接

    Ivony 2010-06-09 00:49:44

    @infinte

    呃,现在才看到,的确是,我俩的方案应该是同一套。虽然看的晕乎乎的,但提供each而不是next这一点上应该是一样的。

    至于yield break,似乎理解有些问题,yield break和yield continue其实是C#的那种解决方案特有的。如果采用这种方案的话,其实是没有必要什么yield break的。直接break就好了。

  61. Dexter.Yy
    116.232.8.*
    链接

    Dexter.Yy 2010-06-09 00:59:25

    如果只是为了快速生成迭代器,不在乎副作用的话……

    function generator(fn, args){
        var queue, cache = [];
        args.push(yield);
        fn.apply(this, args);
        init();
        return {
            next: next,
            close: init
        };
    
        function yield(result){
            cache.push(result);
        }
        function next(){
            return queue.pop();
        }
        function init(){
            queue = cache.slice().reverse();
        }
    };
    
    function foo(a, b, yield){
        for (var i = 0; i <= 10; i++)
            yield(a + b + i);
    }
    
    foo = generator(foo, [1, 2]);
    
    console.log(foo.next())
    console.log(foo.next())
    console.log(foo.next())
    foo.close()
    console.log(foo.next())
    
    function forEach(iter, fn, context){
        var result, i = 0;
        iter.close();
        while (result = iter.next()) {
            fn.call(context || window, result, i++);
        }
    }
    
    forEach(foo, function(a, i){
        console.log(i, a);
    });
    
  62. vczh
    58.38.56.*
    链接

    vczh 2010-06-09 02:16:08

    @老赵: 好像大家都忽略了实现infinity_array |> take(10)的这个重要东西……

    不断走,边走边计数,走到一定程度用异常中断掉就可以了。

  63. 链接

    Ivony 2010-06-09 02:35:19

    @vczh

    其实是一样的么,

    Take实现参考:

    function Take(enumerator, size)
    {
        return function (fun)
        {
            enumerator(function (item)
            {
                if (size-- == 0)
                    return true;
                else
                    return fun(item);
            });
        }
    } 
    

    无限集:

    function fun(yield)
    {
        var i = 0;
    
        while (true)
            yield(i++);
    }
    

    参考测试:

    Take(yieldHost(fun), 10)(function (item)
    {
        window.alert(item);
    });
    
  64. Dexter.Yy
    116.232.8.*
    链接

    Dexter.Yy 2010-06-09 03:00:16

    刚才突然想起来,之前写的那个生成器其实更大程度上只是个实现接口的装饰器,而生成器本身的功能,就算没有yield,在js里也可以很便捷的用curring来实现

    比如,如果要让上面那段代码避免一开始就对整个序列求值,支持无限的序列,那么可以改成这样:

    function generator(fn, args){
        var routine, self = this;
        args.push(_yield);
        init();
        return {
            next: next,
            close: init
        };
    
        function _yield(result){
            return result;
        }
        function next(){
            return routine.apply(self, arguments);
        }
        function init(){
            routine = fn.apply(self, args);
        }
    }
    
    function fibonacci(n, _yield) { 
        var n1 = n2 = s = i = 1;
        return function(){
            for(; i<n; i++){
                s = n1 + n2;
                n1 = n2;
                n2 = s;
                return _yield(n1);
            }
        };
    }
    
    fibIter = generator(fibonacci, [1000]);
    
    console.log(fibIter.next()) // 1
    console.log(fibIter.next()) // 2
    console.log(fibIter.next()) // 3
    console.log(fibIter.next()) // 5
    console.log(fibIter.next()) // 8
    console.log(fibIter.next()) // 13
    fibIter.close()
    console.log(fibIter.next()) // 1
    console.log(fibIter.next()) // 2
    console.log(fibIter.next()) // 3
    

    可以看到_yield其实是多余的,其实只需要这样:

    function fibonacci() { 
        var n1 = n2 = s = i = 1;
        return function(){
            while (true){
                i++;
                s = n1 + n2;
                n1 = n2;
                n2 = s;
                return n1;
            }
        };
    }
    
    
    function forEach(generator, fn, context){
        var result, i = 0;
        iter = generator();
        while (result = iter()) {
            if (false === fn.call(context || window, result, i++))
                break;
        }
    }
    
    forEach(fibonacci, function(a, i){
        console.log(i + ": " + a);
        if (i >= 10)
            return false;
    });
    
    /*====结果====
        0: 1
        1: 2
        2: 3
        3: 5
        4: 8
        5: 13
        6: 21
        7: 34
        8: 55
        9: 89
        10: 144
      ============*/
    
  65. Ian Yang
    218.82.138.*
    链接

    Ian Yang 2010-06-09 04:58:39

    代码有点长,贴在gist了。

    http://gist.github.com/430615#file_yield.js

    主要思想就是把Enumerator里的程序分段存下来,然后手动控制执行。利用闭包保存状态。next()有负作用,懒得改了。

    • _s是一段不包含其它_开头函数的block.
    • _while, _if如字面
    • _yield 即yield

    参数都需要函数。

    run函数返回true时,表示yield了,这时next()返回。run返回false时,表示该段代码执行完毕。

    其它语句如break, continue可以用类似方式加上。

    灵感主要来自boost::lambda

    好久没弄Javascript,不知道怎么样能去掉this前缀直接调用这些函数。

  66. 老赵
    admin
    链接

    老赵 2010-06-09 10:06:40

    @Ivony 其实是一样的么, Take实现参考:

    function Take(enumerator, size)
    {
        return function (fun)
        {
            enumerator(function (item)
            {
                if (size-- == 0)
                    return true;
                else
                    return fun(item);
            });
        }
    }
    

    喔,好像用return true和return fun(item)不是很合适的样子……有机会我仔细写一个完整的来试试看。

  67. 老赵
    admin
    链接

    老赵 2010-06-09 10:09:51

    @Ian Yang

    兄弟幸苦了,有机会我仔细看看。

  68. 老赵
    admin
    链接

    老赵 2010-06-09 10:11:11

    @infinte: 你最好做个颁奖仪式,最好看奖、最牛叉奖…………另外,用异常来做break的始作俑者好像是我吧……

    这个评奖我评不来啊……要不颁给你个“异常中断奖”吧,哈哈。

  69. 4搂的
    61.172.247.*
    链接

    4搂的 2010-06-09 10:37:12

    function Range(minInclusive, maxExlusive)
    {
        var i = minInclusive;
        return function (){
            return {value:i++,next:i<maxExlusive?arguments.callee:null};
        }()
    }
    
    function OneToThree()
    {
        return function a(){return {value:2,next:c};}();
        function b(){return {value:2,next:c};}
        function c(){return {value:3,next:null};}
    }
    
  70. 链接

    陈梓瀚(vczh) 2010-06-09 11:41:18

    于是,大家已经完全忘记了返回一个迭代器的好处了……

  71. 链接

    Ivony 2010-06-09 12:49:14

    @陈梓瀚(vczh)

    我也在想这个问题,yield要实现的多完美都没问题(玩过火了还能利用解释执行)。但如果只是为了实现而实现,丧失了实用价值,或者代码让人难以理解和扩展了,就纯趣味了。。。。

    有时间我打算完整实现Enumerable里面的那些东西,顺带看看在JavaScript里面怎么去做扩展方法的语法。顺便,把jQuery也给整合起来,,,,

    还有,现在的实现还是enumerator,还没有实现enumerable(因为enumerator实例非线程安全,所以有些时候还需要enumerable)。

  72. 4搂的
    61.172.247.*
    链接

    4搂的 2010-06-09 13:57:24

    function fibSeq() {
        var a = [0, 1];
        var curr = 0;
        return new Iterator(function(){
            if(curr>1) this.value=a[curr]=a[curr-1]+a[curr-2];
            else this.value = a[curr];
            curr++;
            return true;
        });
    }
    function Iterator(next)
    {
        this.next = next;
        this.takeWhile = function(filter){
            return new Iterator( function(){ return next.call(this) && (!('value' in this) || filter(this.value))});
        }
        this.sum =function(){
            var sum = 0;
            while(this.next())
            {
                sum += this.value;
            }
            return sum;
        }
    }
    function toIter(o){
        if(o instanceof Iterator) return o;
        else return new Iterator(o.next);
    }
    alert(toIter(fibSeq()).takeWhile(function (i) {return i <= 3}).sum());
    
  73. 老赵
    admin
    链接

    老赵 2010-06-09 14:15:05

    @4搂的

    兄弟您登录以后,想发就发,想改就改,想删就删,比什么都好。

  74. 链接

    4楼的 2010-06-09 14:19:39

    谁让你不支持盛大通行证的 我就不登录 哈哈哈

  75. 老赵
    admin
    链接

    老赵 2010-06-09 14:24:41

    @4楼的

    登录了就换个名字嘛,好认,嘿嘿。

  76. 链接

    winter 2010-06-09 14:39:33

    呵呵 好 换了

    别光说登录的事 看看我的代码啊 呵呵

  77. 老赵
    admin
    链接

    老赵 2010-06-09 15:57:35

    @winter

    我发现你这个还是最传统的迭代器的实现方式,而且似乎依旧不是通用的编程结构,只是用了闭包和first-class function简化了Java里面新建一个类的代码。

  78. 老赵
    admin
    链接

    老赵 2010-06-09 16:02:54

    贴一下我的代码,看了这个以后,相信大家也就能够猜出具体的实现方式了,不过详细分析等等还是等下一篇文章吧,呵呵。

    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));
    
        });
        });
    }
    

    简单地说,就是monad形式的。暂时说来用递归代替循环,如果要支持循环的话,就在yield和yieldSeq外再补充一个while结构。

  79. 链接

    winter 2010-06-09 17:27:01

    这个嘛 其实传统的类结构是因为takeWhile和sum才加上的 注意看 那个next函数的上下文其实是在fibSeq里面的

    我写了几句之后 就觉得好像没什么可封装的 不管怎么封装终究还是"返回function"

  80. 啊立
    122.224.94.*
    链接

    啊立 2010-06-10 16:32:54

    赵哥,不去北大青鸟,那去哪个学校学编程嘞??

  81. 啊立
    122.224.94.*
    链接

    啊立 2010-06-10 16:33:38

    我就喜欢编程,不爱语数外,所以没考上大学,,,咋办呐?

  82. 老赵
    admin
    链接

    老赵 2010-06-10 18:06:11

    @啊立: 我就喜欢编程,不爱语数外,所以没考上大学,,,咋办呐?

    放弃编程或喜欢上数外吧。

  83. 老菜
    60.215.31.*
    链接

    老菜 2010-06-10 22:05:13

    感觉几天没过来,老赵写了好多文章啊。慢慢学习。

  84. V
    203.95.110.*
    链接

    V 2010-06-11 17:18:00

    老赵,如果我有想了解学习.net编译器,应该阅读哪些书籍呢?多谢

  85. 老赵
    admin
    链接

    老赵 2010-06-11 20:50:48

    @V

    什么叫做.NET编译器?C#编译器这种就看龙书吧,JIT编译器可以看看虚拟机方面的内容。话说Rfx老大最近推荐了一本Oracle JRockit: The Definitive Guide,应该值得一看。

  86. 使用了infinte的异常跳出法
    125.95.12.*
    链接

    使用了infinte的异常跳出法 2010-06-14 09:18:09

    function OneToThree(){
        this.yield(1);
        this.yield(2);
        this.yield(3);
    }
    
    function Range(min, max) {
        return function(){
            for (var  i = min; i < max; i++) this.yield(i);
        }
    }
    
    function fibSeq() {
        var i = 0, j = 1;
        return function(){
            while (true) {
                this.yield(i);
                var t = i;
                i = j;
                j += t;
            }
        }
    }
    
    var toIter = function(list){
        if(!(this instanceof toIter)){ return new toIter(list);}
        this.values = [];
        this.list = list;
        this.rule = function(){}
    }
    toIter.prototype = {
        yield: function(value){
            if(this.rule(value)){ this.values.push(value); }else{ throw toIter; }
        },
        Take: function(n){
            var counter = 0;
            return this.takeWhile(function(){ return counter++ < n; });
        },
        takeWhile: function(filter){
            this.rule = function(value){ return filter(value); }
            this.values.length = 0;
            try{ this.list(); }catch(e){ if(e != toIter) throw e; }
            return this;
        },
        Sum: function(){
            var ret = 0, values = this.values, n = values.length;
            while(n--){ ret += values[n]; }
            return ret;
        }
    }
    
    document.write(toIter(OneToThree).Take(2).values);
    document.write("<br>");
    document.write(toIter(Range(10,50)).Take(20).values);
    document.write("<br>");
    document.write(toIter(fibSeq()).Take(10).values);
    document.write("<br>");
    var iter = toIter(fibSeq()).takeWhile(function (i) { return i <= 5});
    document.write(iter.values.join("+")+"="+iter.Sum());
    
  87. 使用了infinte的异常跳出法
    125.95.12.*
    链接

    使用了infinte的异常跳出法 2010-06-14 14:59:10

    还可以定义一个yield全局函数就连this.都省了

  88. 使用了infinte的异常跳出法
    125.95.12.*
    链接

    使用了infinte的异常跳出法 2010-06-14 16:33:31

    异常跳出就不能继续就不能next了 最后写出的方法跟你的差不多 想不到老赵的js水平也这么高 佩服佩服

  89. yang
    125.37.112.*
    链接

    yang 2011-03-09 11:46:14

    js里没有睡眠功能,怎么办,我想用javascript去调用php的sleep()行不行

  90. 老赵
    admin
    链接

    老赵 2011-03-09 14:54:45

    @yang

    看Jscex这个东西吧。

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我