Lua中有状态和无状态迭代器之间的区别 [英] Difference between stateful and stateless iterators in Lua

问题描述

Lua中的无状态迭代器和有状态迭代器有什么区别，请详细说明?何时需要使用无状态迭代器?何时需要使用无状态迭代器?我需要一些例子来理解这个概念.

What is difference between stateless and stateful iterators in Lua, explain in detail please?When do we need to use stateless and when the other one? I need examples to understand the concept.

推荐答案

首先让我们在定义上达成一致:(在Lua中)迭代器是类似于 function 的对象，它会在顺序，每次被调用.我认为这样做有助于重写for迭代，如Lua ref手册中所述:

First let's agree on a definition: (in Lua) an iterator is a function-like object that returns the next value in a sequence, every time it is called. I think it helps to rewrite the for iteration as done is Lua ref manual:

for itemlist in expression do block end

在逻辑上等效于(伪代码):

is logically equivalent to (pseudocode):

do
    local func, seq, controlVar = expression
    while true do
        local itemlist = func(seq, controlVar)
        if first of itemlist == nil then break end
        controlVar = first of itemlist

        block (which uses items in itemlist)
   end
end

其中expression是数据的三元组(或返回此类三元组的函数调用):

where expression is a triplet of data (or a function call that returns such a triplet):

• func是实际的迭代器函数
• seq是要迭代的序列
• controlVar是循环控制变量

• func is the actual iterator function
• seq is the sequence being iterated over
• controlVar is the loop control variable

迭代状态是在迭代序列中查找下一项所需的任何状态.因此，无状态迭代器是func不包含任何这样的状态的迭代器:您可以随时调用func(seq, controlVar)，返回值将始终相同(如果seq不变)；否则，返回值将始终相同.它不取决于呼叫之前发生的情况.

Iteration state is any state that could be needed to find the next item in the sequence being iterated over. A stateless iterator is therefore one where func does not contain any such state: you can call func(seq, controlVar) at any time, the return value will always be the same (if seq has not changed); it does not depend on what happened before the call.

如上所示，Lua支持一个循环控制变量.因此，为了使序列可通过无状态迭代器进行迭代，必须有可能基于 one 循环控制变量来确定序列中的下一项.即，必须有可能单独从(s，controlVar)"中找出下一个项目". ipairs()生成执行此操作的迭代器:ipairs(s)返回三元组(iterFunction, s, 0);可以给iterFunction和s加上索引0，然后返回1, s[1]，然后返回2, s[2]，依此类推(对于N个项目的表，最终什么也没有).

As seen above, Lua supports one loop control variable. So in order for a sequence to be iterable via a stateless iterator, it must be possible to determine the next item in the sequence based on one loop control variable. I.e., it must be possible to figure out "next s item" from "(s, controlVar)" alone. The ipairs() generates an iterator that does this: ipairs(s) returns the triplet (iterFunction, s, 0); the iterFunction can be given s and the index 0, and returns 1, s[1], then 2, s[2], etc (eventually nothing for a table of N items).

如果要查找序列中的下一项需要多个循环控制变量怎么办?还是取决于其他变量的状态，这些变量应在迭代过程中保存?示例:

What if finding the next item in a sequence requires more than one loop control variable? Or depends on the state of other variables, which should be saved during iteration? Example:

一个无休止的迭代器可能需要跟踪第一"项，以便一旦到达序列的末尾，它就可以在第一项中恢复； 图迭代器可能需要在深度优先搜索中跟踪最近的同级"，以便一旦到达分支的末尾，就可以继续下一个最近的同级.

• an endless iterator may need to keep track of "first" item so that once the end of sequence is reached, it can resume at first item;
• a graph iterator may need to keep track of "most recent sibling" in a depth first search so that once the end of a branch is reached, it can continue with next most recent sibling.

有状态迭代器保存有关迭代的状态，以便可以找到下一项.在Lua中，如果迭代器函数是闭包(具有升值的函数)或函子(充当函数的表，即具有__call元方法)，则可能发生这种情况. up值(关闭)或数据成员(functor)可以存储所需的状态.

A stateful iterator holds state about the iteration so that the next item can be found. In Lua this is possible if the iterator function is a closure (a function with upvalues) or a functor (a table that behaves as a function, i.e. has a __call metamethod). The up values (closure) or the data members (functor) could store the required state.

无状态迭代器始终可以包装到有状态迭代器中.对于ipairs:

A stateless iterator can always be wrapped into a stateful iterator. For ipairs:

function statefulIpairs(s)
    local f, s, var = ipairs(s)
    return function() 
        local i, v = f(s,var)
        var = i
        return i, v
    end
end

此后可以称为

tbl = {'a', 'b', 'c', 'd'}
sip = statefulIpairs(tbl) -- sip is stateful iter specific to tbl
for i,v in sip() do print(i,v) end

有状态迭代器的开发者决定迭代器具有什么功能:迭代器的API可能允许倒带，反转方向或其他操作.在闭包的情况下，这甚至是可能的:附加参数可用于访问附加功能.例如，接受第三个参数，当该参数为非nil时，它将重置为序列的开头:

A developer of a stateful iterator decides what capabilities the iterator has: the iterator's API may allow for rewind, inverting the direction, or other operations. This is even possible in the case of closures: additional parameters can be used to access the additional capabilities. Example, accept a third parameter which, when non nil, resets to beginning of sequence:

function resetableStatefulIpairs(s)
    local f, s, var = ipairs(s)
    local start = var
    return function(a,b,reset)
        if reset ~= nil then var = start; return end        
        local i, v = f(s,var)
        var = i
        return i, v
    end
end

sip = resetableStatefulIpairs(tbl) -- sip is stateful iter specific to tbl
for i,v in sip() do print(i,v) end
sip(nil, nil, true) -- reset it
for i,v in sip() do print(i,v) end

Update 一个更整洁的示例是如何生成一个接受命令的函数迭代器，以便您可以"...在序列中的任何位置停止并在序列的其余部分迭代3次"(如@deduplicator请求):

Update A neater example is how to generate a function iterator that accepts commands such that you can "...stop anywhere in the sequence and iterate over the rest of the sequence 3 times" (as requested by @deduplicator):

function iterGen(seq, start)
    local cvar = start or 1
    return function(cmd) 
        if cmd == nil then
            if cvar > #seq then return nil, nil end
            val = seq[cvar]
            cvar = cvar + 1
            return cvar-1, val

        else
            cmd = cmd[1]
            if cmd == 'rewind' then
                cvar = start or 1

            elseif cmd == 'newstart' then
                start = cvar
            end
        end
    end
end

具有以上条件:

> s = {1,2,3,4,5,6,7}
> iter = iterGen(s)
> for i,v in iter do print(i,v); if i==3 then break end  end
1       1
2       2
3       3
> iter {'newstart'} -- save current as the new start pos
> for i,v in iter do print(i,v)  end -- continue till end
4       4
5       5
6       6
7       7
> iter {'rewind'}
> for i,v in iter do print(i,v)  end
4       4
5       5
6       6
7       7
> iter {'rewind'}
> for i,v in iter do print(i,v)  end
4       4
5       5
6       6
7       7

如所示，有状态迭代器没有什么特殊之处，除了迭代状态在迭代器内部，因此，如上所述，开发人员可以在上面公开诸如rewind和newstart之类的所需功能.使用无状态迭代器，没有任何限制.

As demonstrated, there is nothing special about stateful iterators except for the fact that the state of iteration is inside the iterator, so as stated, it is up to the developer to expose desired functionality like rewind and newstart above. With stateless iterators, there are no limits.

将迭代器设计为函子将是一种更自然的API，因为此后，迭代器函数"具有可以调用的方法"，但是创建一个可命令的函数是一个有趣的挑战.

It would be a more natural API to design the iterator as a functor, since then the iterator "function" has "methods" which can be called, but it was an interesting challenge to create a commandable function.

这篇关于Lua中有状态和无状态迭代器之间的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！