Lua基础 generic for

逃离我推掉我的手 2022-03-19 07:48 315阅读 0赞

下面写一下怎么给generic***for ***写迭代器。

# 1. 迭代器和闭包 #

在Lua中，迭代器用function表示，每次调用该function，都会返回集合中的next元素。

每个迭代器都要在连续的调用之间保存一些state，这样才能知道进行到哪一步，下一步该从哪开始处理。在Lua中，闭包可以处理这个问题。闭包结构包含两个function：一个是闭包本身，另一个是factory，用来创建闭包。下面是个简单的示例：

function values(t)
        local i = 0
        return function () i = i + 1; return t[i] end
    end

在上面的例子中，values是factory。每次调用factory，都会创建一个新的闭包（迭代器本身）。该闭包在变量t和i中保存state。每次调用这个迭代器，都会从t中返回next元素的值。返回最后一个元素后，它会返回nil，标志着迭代器结束。

可以将上面的迭代器用在***while ***中,但是用generic***for ***更简单：

t = {10, 20, 30}
    
    
    function value(t)
        local i = 0
        return function () i = i + 1; return t[i] end
    end
    
    
    iter = value(t)
    while true do
        local element = iter()
        if element == nil then break end
        print(element)
    end
    
    
    t = {1, 2, 3}
    for element in value(t) do
        print(element)
    end

执行结果如下：

![1364879269_8358.PNG][]

generic***for ***为迭代器循环过程在内部保存state，不需要iter变量；每次迭代都调用该迭代器，并在迭代器返回nil时停止循环。

下面是一个复杂点的例子，从当前输入的文件中遍历所有的word。遍历过程中保存两个值：当前行（变量line），当前位置（pos），***string.find ***函数从当前行中搜索一个word，用'%w+'匹配，在匹配到word后，将当前位置pos置于该word之后的第一个字符处，并返回该word。否则，迭代器读入一个新行再重复上面的过程。如果没有更多的行，返回nil，标志迭代结束。

function allwords ()
        local line = io.read()
        local pos = 1
        print("allwords begin")
        return function ()
            while line do
                local s, e = string.find(line, "%w+", pos)
                if s then
                    pos = e + 1
                    print("return the word")
                    return string.sub(line, s, e)
                else
                    print("read next line")
                    line = io.read()
                    pos = 1
                end
            end
            print("return nil, iter end")
            return nil
        end
    end
    
    for word in allwords() do
        print(word)
    end

执行结果如下：

![1364878989_7554.PNG][]

注意执行打印出来的一些信息，可以帮助了解脚本的执行过程。

# 2. Generic***for ***的语义 #

前面的例子有一个缺陷，每次都需要创建一个新的闭包来初始化一个新的循环。大多数情况下，这不是什么太大的开销。但是，有时也是不能接受的。这时就需要用generic***for ***本身来保存迭代器状态。

Generic***for ***会保存3个值：iterator function， invariant state，control variable。generic***for ***的语法如下：

for <var-list> in <exp-list> do
        <body>
    end

这里，var-list是一个或多个变量的名字，用逗号分隔，exp-list是一个或多个表达式，也用逗号分隔。通常exp-list只有一个元素，对iterator factory的调用。例如：

for k, v in pairs(t) do print(k, v) end

var-list是k，v， exp-list是pairs(t)。通常，var-list也只有一个变量，如下：

for line in io.lines() do
        io.write(line, "\n")
    end

var-list的第一个变量为control variable，它的值为nil时表示循环结束。

***for ***循环先计算in后面的表达式的值，这些表达式会产生3个值，就是上面写的generic***for* **需要保存的3个值：iterator function， invariant state，control variable 的初始值。跟多赋值语句一样，只有最后一个表达式可以产生多个值；但是所有的表达式的结果最终被调整为3个，多的丢弃，少的补nil （当使用简单的迭代器的时候，factory只返回iterator function，invariant state和control variable的值为nil）。

完成上面的初始化步骤后，***for** *用invariant state和control variable作为参数来调用iterator function。然后***for** *将iterator function返回的值赋值给var-list中的变量，如果返回的第一个值为nil，那么循环结束。否则，***for** *执行循环体代码并再次调用iteration function，重复上面的过程。

下面的伪代码也许能帮助理解：

for var_1, ..., var_n in <explist> do <block> end

等价于：

do
        local _f, _s, _var = <explist>
        while true do
            local var_1, ... , var_n = _f(_s, _var)
            _var = var_1
            if _var == nil then break end
            <block>
        end
    end

如果iterator function为*f* ，invariant state为*s* ， control variable的初始值为*a0*，control variable会如下循环：

*a1* =*f* (*s *,*a0 *),*a2* =f (*s *, *a1 *), *a3* =*f* (*s *,*a2 *), ....

直到ai为nil。

# 3. 无状态迭代器 #

顾名思义，无状态迭代器自身不会保存任何state。因此，我们可以在多次循环里面用同一个迭代器，避免了创建新闭包的开销。

每次迭代，for 循环用两个参数 invariant state 和 control variable 来调用 iterator 函数。ipairs 是个典型的此类迭代器：

a = {"one", "two", "three"}
    for i, v in ipairs(a) do
        print(i, v)
    end

迭代器的state 是被遍历的table ，当前的index 是 control variable 。ipairs 和 iterator 实现都比较简单，下面是一个示例：

local function iter (a, i)
        i = i + 1
        local v = a[i]
        if v then
            return i, v
        end
    end
    
    function ipairs (a)
        return iter, a, 0
    end

在for 循环中，Lua调用 ipairs(a) ，得到3个值： iter 函数为iterator ， a 为invariant state ， 0 是control variable 的初始值。 然后，Lua调用 iter(a，0)， 得到1， a\[1\] 。下一次迭代，调用 iter(a，1)， 得到 2， a\[2\]，直到第一个nil值，迭代结束。

pairs 函数跟上面的 ipairs 类似，只是iterator 函数为 next， 不是iter。next 是Lua中的一个基本函数：

function pairs (t)
        return next, t, nil
    end

next(t, k) 调用，k 是 table t 中的一个key ，返回两个值，next key 和 t\[next key\]，next(t, nil)返回 table 中的第一对值。例如：

![1365484638_9129.PNG][]

很多人比较喜欢直接用next ，而不是用pairs：

for k, v in next, t do
        <loop body>
    end

for 循环的exp-list会被调整为3个值，Lua会得到next，t，nil，跟调用pairs(t)得到的结果是一样的。

下面是一个遍历链表的例子，代码有点绕，仔细想一下就会明白的。

local function getnext (list, node)
        return not node and list or node.next
    end
    function traverse (list) 
        return getnext, list, nil 
    end
    
    list = nil
    for line in io.lines() do
        list = {val = line, next = list}
    end
    
    for node in traverse(list) do
        print(node.val)
    end

# 4. 复合状态的迭代器 #

很多时候，需要保存的state，除了 invariant state 和 control variable 还有别的。这种情况，用闭包是最简单的方案。还有一个可选方案，用table，把所有需要保存的东西都打包到table 中，想保存什么就把什么打包到table 中。在循环过程中，尽管state 始终是同一个table，但是table中的数据可以在循环过程中更改。迭代器把所有需要的数据到封装到table 中，所有就忽略了generic *for* 提供的第二个参数。

下面把allwords那个示例改写了一下，来展示一下上面所说的用法

local iterator                                                                                              
    function allwords()
        local state = {line = io.read(), pos = 1}
        return iterator, state
    end
     
    function iterator(state)
        while state.line do
            --search for next word
            local s, e = string.find(state.line, "%w+", state.pos)
            if s then
                -- update next position (after this word)
                state.pos = e + 1 
                return string.sub(state.line, s, e)
            else
                state.line = io.read()
                state.pos = 1 
            end 
        end 
        return nil 
    end
     
    for word in allwords() do
        print(word)
    end

运行结果示例如下：

![1365510526_3270.PNG][]

我们应该尽可能的使用无状态的迭代器，将所有的state都保存到*for* 循环的变量中。在开始新的循环的时候就不需要创建新的对象。当你的迭代器不适合上面说的table的情况时，应该用闭包。用闭包更简洁优美，并且效率更高，因为：1. 创建闭包比创建table开销要小。 2. 访问非局部变量（闭包中）比访问table的域要更快。 后面还会讲讲用*coroutines* 来实现迭代器，更强大，但是代价也更高。

# 5. 真正的迭代器 #

“迭代器”这个名字其实有点误导，因为我们的“迭代器”根本不做迭代操作，真正去做迭代操作的是 for 循环。“迭代器”只是为迭代过程提供连续的值。可能更好的名字应该叫“生成器”。

不过，下面展示一种真正去做迭代操作的“迭代器”，再把allwords 重写一次：

function allwords(f)                                                                                        
        for line in io.lines() do
            for word in string.gmatch(line, "%w+") do
                f(word) -- call the function
            end 
        end 
    end
     
    allwords(print)
     
    print("=============================")
    local count = 0 
    allwords(function(w) if w == "hello" then count = count + 1 end end)
    print("the number of 'hello' is " .. count)

示例中 的参数f 可以传相关的函数，示例中简单的用了*print* 来显示了一下句子中的word，用了一个匿名函数统计句子中的“hello”个数。

执行结果如下：

![1365511713_9251.PNG][]

这种形式的迭代器在旧版本的Lua中很流行，那是Lua没有*for* 语句。跟“生成器”形式的迭代器比起来，到底哪一种好呢？两种开销差不多，每次迭代都是一次函数调用。从一方面讲，这种旧式迭代器，更容易写。但是“生成器”形式的迭代器更灵活。首先，她可以同时进行两个平行的迭代（例如，比较两个句子中的word，一个一个的比），另外，可以用*break* 在迭代过程中退出。总的来说，“生成器”形式的迭代器也许更受欢迎一点。

水平有限，如果有朋友发现错误，欢迎留言交流。

[1364879269_8358.PNG]: https://img-my.csdn.net/uploads/201304/02/1364879269_8358.PNG
[1364878989_7554.PNG]: https://img-my.csdn.net/uploads/201304/02/1364878989_7554.PNG
[1365484638_9129.PNG]: https://img-my.csdn.net/uploads/201304/09/1365484638_9129.PNG
[1365510526_3270.PNG]: https://img-my.csdn.net/uploads/201304/09/1365510526_3270.PNG
[1365511713_9251.PNG]: https://img-my.csdn.net/uploads/201304/09/1365511713_9251.PNG