Iterator是一种允许你遍历一个集合中元素的结构. 在Lua中, 我们可以用function实现iterator, 每次调用这个函数, 它都返回集合中的下一个元素. 一个iterator需要保留一些用来遍历的信息, 例如当前元素的位置以及什么时候结束. Closure的机制非常适合这个工作. 遍历所需的环境变量可以保存在upvalue中, 这样每一次调用这个closure, 他都返回遍历某一个list的iterator. 由于这样的Closure是用来产生iterator的, 我们称这样的closure为iterator factory.
每一次
以下是一个简单的iterator factory, 用来遍历一个table.
function list_iter (t)
local i = 0
local n = table.getn(t)
return function ()
i = i + 1
if i <= n then return t[i] end
end
end
在这里, 每一次我们调用list_iter, 返回一个iterator, 这个iterator使用i, n来保存遍历时所需要的环境信息. 每一次我们调用这个iterator返回被遍历list的下一个值. 如果在我们遍历的list已经达到最后一个元素, 那么返回nil.
我们可以这样使用这个iterator:
t = {10, 20, 30}
iter = list_iter(t) -- creates the iterator
while true do
local element = iter() -- calls the iterator
if element == nil then break end
print(element)
end
我们也可以使用generic for循环, 这样功能相同, 但是代码更少:
t = {10, 20, 30}
for element in list_iter(t) do
print(element)
end
相比一般循环, generic for多做了一些事情, 它内部调用iterator factory产生iterator, 然后将iterator保存起来依次调用, 当iterator返回nil的时候退出循环.
以下是另一个iterator factory的例子:
function allwords ()
local line = io.read() -- current line
local pos = 1 -- current position in the line
return function () -- iterator function
while line do -- repeat while there are lines
local s, e = string.find(line, "%w+", pos)
if s then -- found a word?
pos = e + 1 -- next position is after this word
return string.sub(line, s, e) -- return the word
else
line = io.read() -- word not found; try next line
pos = 1 -- restart from first position
end
end
return nil -- no more lines: end of traversal
end
end
虽然iterator factory有些复杂, 但是使用很简单直观:
for word in allwords() do
print(word)
end
一般说来, iterator是使用简单但是实现困难. 幸运的是多数情况下开发人员都不需要自己实现iterator而使用库中间已经定义好的iterator即可.
The Semantics of the Generic for
在上面我们使用upvalue用来保存iterator时所需要的环境信息, 其实Generic for就有保存iterator时所需要的环境信息的功能, 这样可以使代码更简洁高效.
Generic for的一般形式如下:
for <var-list> in <exp-list> do
<body>
end
<var-list>是一些变量的list, 以逗号分隔, <exp-list>是一些表达式的list, 以逗号分隔. 大多数情况<exp-list>只包含一个调用iterator factory的表达式:
for k, v in pairs(t) do
print(k, v)
end
<var-list>中的变量多数情况下也只有一个:
for line in io.lines() do
io.write(line, '\n')
end
在<var-list>中的第一个变量称为控制变量, 如果它的值为nil, 那么循环退出. 在执行时首先会计算<exp-list>中的表达式, <exp-list>应该返回3个元素, 第一个是iterator function, 第二个是一个常量用来记录一些环境信息, 最后一个是控制变量的初值.
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
a = {"one", "two", "three"}
for i, v in ipairs(a) do
print(i, v)
end
可以看出, 以下表达式
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
Stateless Iterators
Stateless Iterator就是不含状态和环境信息的iterator. 如同上面所说的,Stateless Iterator的遵从Generic For的约定, 主要靠Generic For来保存状态和环境信息.
a = {"one", "two", "three"}
for i, v in ipairs(a) do
print(i, v)
end
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
当Generic For调用ipairs时, 他返回三个值, 分别为iterator function, invariant state和control value. 以后每次进入循环调用iter函数时使用两个参数, invariant state和control value.