lua - 下面的Lua迭代器是无状态的吗？

Question

我对无状态迭代器的概念感到困惑。作为练习，我编写了一个迭代器来打印给定字符串的所有非空子字符串。代码如下。

local function iter(state, i)
    local str = state.str
    if type(str) ~= "string" or str == "" then return nil end
    if state.ending > #str then return nil end

    local start = state.start
    local ending = state.ending

    if start == ending then
        state.ending = ending + 1
        state.start = 1
    else
        state.start = start + 1
    end

    return string.sub(str, start, ending)
end

function allSubstrings(str)
    return iter, { str = str, start = 1, ending = 1 }, nil
end

for substr in allSubstrings("abcd123") do
    print(substr)
end

我使用一个表{ str = str, start = 1,ending = 1 }作为所谓的不变状态，但是我必须在中更改这个表中的字段iter 本地函数。那么这个迭代器是无状态的还是具有复杂状态的？如果它不是无状态的，有没有办法用无状态迭代器实现这个功能？

谢谢。

Answer 1

PIL-chapter about stateless iterators状态:

As the name implies, a stateless iterator is an iterator that does not keep any state by itself. Therefore, we may use the same stateless iterator in multiple loops, avoiding the cost of creating new closures.

在代码中，这意味着两个 for 循环:

f, s, var = pairs( t )
for k,v in f, s, var do print( k, v ) end
for k,v in f, s, var do print( k, v ) end

应该产生相同的输出。仅当不变状态 s 和迭代器函数 f 的任何上值在迭代过程中都没有改变时才有效，否则第二个 for 循环将具有与第一个循环不同的起始条件。

所以，不，您的迭代器不是无状态迭代器，因为您在迭代期间更改了不变状态。

有一种方法可以让你的迭代器无状态(流行的 Lua 库 luafun 广泛使用这种技术):将所有可变状态保留在循环控制变量 var 中(即使你需要在每个分配步骤中分配一个新表):

local function iter( str, var )
  if type( str ) ~= "string" or str == "" then return nil end
  if var[ 2 ] > #str then return nil end
  local start, ending = var[ 1 ], var[ 2 ]
  if start == ending then
    return { 1, ending+1 }, string.sub( str, start, ending )
  else
    return { start+1, ending }, string.sub( str, start, ending )
  end
end

function allSubstrings2( str )
  return iter, str, { 1, 1 }
end

for _,substr in allSubstrings2( "abcd123" ) do
  print( substr )
end

缺点是第一个迭代变量 var (循环控制变量)对于迭代器的用户来说没有任何有用的意义，并且由于您必须为每个迭代步骤分配一个表，因此“避免为另一个循环创建新闭包的成本并不重要。

luafun 无论如何都会这样做，因为它没有能力重新创建迭代器元组(它是通过外部代码的函数参数传递的)，并且对于某些算法，您绝对需要运行相同的算法迭代多次。

此方法的替代方法是将所有可变状态集中在“不变状态”s 中(f 的所有上值必须是不可变的)，并提供一种方法复制/克隆此状态以供以后迭代使用:

f, s, var = allSubstrings("abcd123")
s2 = clonestate( s )
for str in f, s, var do print( str ) end
for str in f, s2, var do print( str ) end

这仍然不是无状态迭代器，但它比具有堆分配循环控制变量的无状态迭代器更节省内存，并且它允许您重新启动迭代。