Lua中有状态和无状态迭代器之间的区别

Question

Lua中的无状态迭代器和有状态迭代器有什么区别,请详细解释一下？我们何时需要使用无状态和另一个？我需要一些例子来理解这个概念.

Answer 1

首先让我们同意一个定义:(在Lua中)迭代器是一个类似函数的对象,每次调用它时都会返回序列中的下一个值.我认为重写for迭代是有帮助的,就像Lua ref手册一样:

for itemlist in expression do block end

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

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是三重数据(或返回这种三元组的函数调用):

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

迭代状态是找到迭代序列中的下一个项目所需的任何状态.因此,无状态迭代器func不包含任何此类状态:您可以随时调用func(seq, controlVar),返回值将始终相同(如果seq未更改); 它不取决于通话前发生的事情.

如上所示,Lua支持一个循环控制变量.因此,为了使序列可以通过无状态迭代器进行迭代,必须能够根据一个循环控制变量确定序列中的下一个项目.也就是说,必须有可能单独从"(s,controlVar)"中找出"下一个项目".的ipairs()生成,这是否一个迭代:ipairs(s)返回三重(iterFunction, s, 0); 在iterFunction可以给出s和索引0,并且返回1, s[1],然后2, s[2],等(最终没有为的N个项目的表).

如果查找序列中的下一个项目需要多个循环控制变量怎么办？或者取决于其他变量的状态,这些变量应该在迭代期间保存？例:

• 无限迭代器可能需要跟踪"第一"项,以便一旦到达序列结束,它就可以在第一项恢复;
• 图形迭代器可能需要在深度优先搜索中跟踪"最近的兄弟",以便一旦到达分支的末尾,它就可以继续下一个最近的兄弟.

有状态迭代器保存有关迭代的状态,以便可以找到下一个项目.在Lua中,如果迭代器函数是一个闭包(具有upvalues的函数)或一个functor(一个表现为函数的表,即具有__callmetamethod),则这是可能的.up值(闭包)或数据成员(functor)可以存储所需的状态.

无状态迭代器总是可以包装到有状态迭代器中.用于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可以允许倒带,反转方向或其他操作.在闭包的情况下甚至可以实现:可以使用附加参数来访问其他功能.例如,接受第三个参数,当非零时,重置为序列的开头:

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

更新一个更简洁的例子是如何生成一个函数迭代器,它接受命令,你可以"......停止序列中的任何地方并迭代序列的其余部分3次"(按照@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.使用无状态迭代器,没有限制.

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