迭代器与通用的 for
在本书中，我们业已用到通用的 for，来完成一些任务了，例如读取文件行，或遍历某个目标上的模式匹配。但是，我们仍然不知道，如何创建咱们自己的迭代器。在本章中，我们将填补这一空白。从简单的迭代器开始，我们将学习如何使用通用 for 的所有功能，来编写各种迭代器。
迭代器与闭包
所谓迭代器，是任何的允许我们遍历集合元素的结构。在 Lua 中，我们通常用函数，来表示迭代器：每次调用该函数，他都会从集合中，返回 “下一个” 元素。典型的例子，是 io.read：每次我们调用他时，他都会返回标准输入文件的下一行，当没有更多行要读取时，就返回 nil。
任何的迭代器，都需要在连续调用之间，保持某种状态，以便知道其所在位置，以及如何在那里继续前进。对于 io.read，C 语言在其流结构中，保留了状态。对于我们自己的迭代器来说，闭包提供了一种很好的保持状态的机制。请记住，闭包是个会访问其外层环境中，一或多个局部变量的函数。在对闭包的连续调用过程中，这些变量会保留他们的值，从而让闭包记住，他在遍历过程中所处的位置。当然，要创建新的闭包，我们就必须创建他的非局部变量。因此，闭包的结构，通常涉及两个函数：闭包本身，与一个创建出闭包及其外围变量的 工厂，factory 函数。
作为示例，咱们来编写一个列表的简单迭代器。与 ipairs 不同，这个迭代器不会返回每个元素的索引，而仅返回其值：
function values (t)
local i = 0
return function () i = i + 1; return t[i] end
end
在本例中，values 便是那个工厂函数。每次我们调用这个工厂，他都会创建出一个新的闭包（迭代器本身）。这个闭包会将其状态，保存在由 values 所创建出的，其外部变量 t 和 i 中。每次我们调用该迭代器时，他都会从列表 t 中，返回下一个值。
咱们可以在 while 循环中，使用这个迭代器：
t = {10, 20, 30}
iter = values(t) -- 创建出迭代器
while true do
local el = iter() -- 调用迭代器
if el == nil then break end
print(el)
end
然而，使用通用的 for，会更加方便。毕竟，他就是为这类迭代设计的：
t = {10, 20, 30}
for el in values(t) do
print(el)
end
通用的 for，完成了迭代循环的所有簿记工作：他内部保留了这个迭代器函数，因此我们不需要那个 iter 变量；他会为每次新的迭代，调用该迭代器；当迭代器返回 nil 时，他就停止循环。(在下一节中，我们将看到通用的 for 所做的，还不止这些。）
作为一个更高级的示例，下图 18.1，“遍历标准输入中所有单词的迭代器”，给出了一个遍历标准输入中，所有单词的迭代器。
function allwords ()
local line = io.read() -- 当前行
local pos = 1 -- 行中的当前位置
return function () -- 迭代器函数
while line do -- 在存在行期间重复
local w, e = string.match(line, "(%w+)()", pos)
if w then -- 发现了一个单词？
pos = e -- 下一位置是在这个单词之后
return w -- 返回这个单词
else
line = io.read() -- 未找到单词；尝试下一行
pos = 1 -- 从首个位置重新开始
end
end
return nil -- 不再有行：遍历结束
end
end
为了完成这个遍历，我们保留了两个值：当前行的内容（变量 line），即我们在这一行的位置（变量 pos）。有了这些数据，我们就总是可以生成下一个单词。其中迭代器函数的主要部分，是调用 string.match，从当前位置开始，检索出当前行中的单词。他使用了模式 "%w+"，描述某个 “单词”，该模式会匹配一或多个字母数字的字符。如果找到某个单词，他将捕获并返回该单词，以及其后第一个字符的位置（以一个空捕获）。然后，该函数会更新当前位置，并返回这个单词。否则，迭代器将读取一个新行，并重复检索。如果不再有行，则返回 nil，表示该迭代的结束。
译注：根据 简单 I/O 模型，这个迭代器工厂的使用，要在
io.input("filename")的上下文中。
尽管其具有一定复杂度，但 allwords 的使用，却很简单：
for w in allwords() do
print(w)
end
这便是迭代器下的常见情况：他们可能不容易编写，但却很容易使用。这并不是什么大问题；通常，以 Lua 编程的最终用户，不会定义迭代器，而只是使用由应用所提供的那些迭代器。
通用 for 的语义
The Semantics of the Generic for
前面那些迭代器的一个缺点是，我们需要创建出一个新的，用来初始化每个新循环的闭包。在很多情况下，这并不是一个真正的问题。例如，在那个 allwords 迭代器中，创建出一个闭包的成本，与读取整个文件的成本相比，可以忽略不计。不过，在某些情况下，这种开销会带来不便。在这种情况下，我们可以使用通用的 for 本身，来保留迭代状态。在本节中，我们将看到，通用的 for，为保持状态所提供的便利。
我们曾看到过，在循环过程中，通用 for 会在内部，保留着迭代器函数。实际上，他保留了三个值：迭代器函数、某种 不变状态，invariant state 及 一个 控制变量，control variable。现在咱们来看看细节。
通用 for 的语法如下：
for var-list in exp-list do
body
end
其中，var-list 是个用逗号分隔的，一或多个变量的列表；exp-list 是个也用逗号分隔的，一或多个表达式的列表。表达式列表通常只会有一个元素，即对某个迭代器工厂的调用。例如，在下面的代码中，变量列表是 k,v，而表达式列表，则只有一个元素 pairs(t)：
for k, v in pairs(t) do print(k, v) end
我们将 var-list 列表中的第一（或唯一一个）变量，称为 控制变量，control variable。在循环过程中，他的值永远不会为 nil，因为当其成为 nil 时，循环就结束了。
for 所做的第一件事，是求得 in 后面表达式的值。这些表达式，应产生由 for 所保留的三个值：迭代器函数、不变状态与控制变量的初始值。与 多重赋值 一样，只有列表中的最后一个（或唯一一个）元素，才可以产生一个以上的值；并且值的数量，会被调整为三个，多余的值会根据需要，丢弃或添加 nil。例如，在我们使用简单迭代器时，迭代器工厂就只会返回迭代器函数，因此不变状态和控制变量，均会得到 nil。
在这个初始化步骤之后，for 会以两个参数，调用迭代器函数：不变状态与控制变量。从 for 结构的角度来看，不变状态没有任何意义。for 只会将初始化步骤中的那个状态值，传递给迭代器函数的所有调用。然后，for 将迭代函数返回的值，赋值给其变量列表中声明的那些变量。如果返回的第一个值（分配给控制变量的那个）为 nil，循环就会终止。否则，for 就会执行其主体，并再次调用迭代函数，重复循环过程。
更确切地说，像下面这种结构
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
因此，在咱们的迭代函数是 f，不变状态是 s，控制变量的初始值是 a0 时，那么控制变量将循环使用 a1 = f(s,a0)、a2 = f(s,a1) 等值，直到 ai 为 nil。如果 for 还有其他变量，他们则只需获得每次调用 f 时，所返回的额外值。
无状态迭代器
Stateless Iterators
顾名思义，无状态迭代器是一种自身不保留任何状态的迭代器。因此，我们可以在多个循环中，使用同一个无状态迭代器，避免了创建新闭包的代价。
正如我们刚才看到的，for 循环会以两个参数：不变状态和控制变量，调用他的迭代器函数。而无状态迭代器，就只使用这两个值，生成迭代的下一元素。这类迭代器的一个典型例子，就是可以遍历某个序列所有元素的 ipairs：
a = {"one", "two", "three"}
for i, v in ipairs(a) do
print(i, v)
end
该迭代的整个状态，是由正被遍历的那个表（即在循环过程中，不会改变的所谓不变状态），与当前索引（控制变量）二者构成。ipairs（迭代器工厂）和迭代器，都很简单；我们可以用 Lua，将他们写成下面这样：
local function iter (t, i)
i = i + 1
local v = t[i]
if v then
return i, v
end
end
function ipairs (t)
return iter, t, 0
end
当 Lua 在 for 循环中，调用 ipairs(t) 时，会得到三个值：作为迭代器的函数 iter、作为不变状态的表 t，以及作为控制变量初始值的 0。然后，Lua 会调用 iter(t, 0)，其结果为 1,t[1]（除非 t[1] 已经是 nil）。在第二次迭代中，Lua 会调用 iter(t,1)，其结果是 2,t[2]，以此类推，直到出现首个 nil 的元素。
对表中所有元素，进行遍历的函数 pairs 与之类似，只是他的迭代函数是 next，而 next 是 Lua 中的一个原语函数，a primitive function in Lua：
function pairs (t)
return next, t, nil
end
next(t,k) 的调用（其中 k 是表 t 的一个键），会以任意顺序，返回表中的下一个键，并将与该键相关的值，作为第二个返回值。next(t, nil) 的调用，会返回第一个键值对。如果没有了更多键值对，next 就会返回 nil。
我们原本可以直接使用 next，而无需调用 pairs：
for k, v in next, t do
-- loop body
end
请记住，for 循环会将其表达式列表，调整为三个结果，从而他会得到 next、t 和 nil；这正是他在调用 pairs(t) 时，所得到的结果。
无状态迭代器的另一个有趣示例，便是遍历某个链表。(链表在 Lua 中并不常见，但有时我们会需要。）我们首先想到的，是只使用当前节点，作为控制变量，这样迭代器函数就可以返回下一节点：
local function getnext (node)
return node.next
end
function traverse (list)
return getnext, nil, list
end
但是，这种实现方式会跳过第一个节点。相反，我们可以使用下面的代码：
local function getnext (list, node)
if not node then
return list
else
return node.next
end
end
function traverse (list)
return getnext, list, nil
end
这里的诀窍，是除了把当前节点用作控制变量外，还讲第一个节点（？译注：不是列表吗？）用作了不变状态（traverse 返回的第二个值）。首次调用那个迭代器函数 getnext 时，node 将为 nil，因此该函数将返回 list 作为第一个节点。在随后的调用中，node 不会为 nil，因此迭代器将如预期，返回 node.next。
按顺序遍历表
Traversing Tables in Order
当程序员试图给表中的条目排序时，就会发生一种常见的混淆。在表中，那些条目构成一个集合，而没有任何的顺序。如果咱们打算对他们进行排序，就必须将其中的那些键，复制到某个数组中，然后对数组排序。
在第 11 章 插曲：高频词 的 “高频词” 程序中，咱们曾看到过这一技巧的示例。下面我们来看另一个例子。假设我们读取了一个源代码文件，并建立了一个，为每个函数名称，提供了定义该函数所在行的表；类似于下面这样的表：
lines = {
["luaH_set"] = 10,
["luaH_get"] = 24,
["luaH_present"] = 48,
}
现在，我们打算按字母顺序，打印出这些函数名。如果我们用 pairs，来遍历这个表，名称就会以任意顺序出现。因为这些名称是表的键，故咱们不能直接对他们排序。但是，如果我们将他们放入某个数组，那么就可以对他们进行排序了。首先，我们必须用这些名字，创建出一个数组，然后对其排序，最后打印结果：
a = {}
for n in pairs(lines) do a[#a + 1] = n end
table.sort(a)
for _, n in ipairs(a) do print(n) end
有人会在这里感到困惑。毕竟，对于 Lua 来说，数组也是没有顺序的（毕竟他们也属于表）。但我们知道怎样计数！因此，在以排序后的索引，访问数组时，我们会强加顺序。这就是为什么，我们应始终使用 ipairs，而不是 pairs 遍历数组。前一函数，强制了键的顺序为 1、2 等，而后一函数，则使用的是表的自然任意顺序（这可能不是我们所需的，但却通常就是这样。）
现在，我们已准备好编写一个按照其键的顺序，遍历某个表的迭代器了：
function pairsByKeys (t, f)
local a = {}
for n in pairs(t) do -- 创建出有着全部键的列表
a[#a + 1] = n
end
table.sort(a, f) -- 对这个列表排序
local i = 0 -- 迭代器变量
return function () -- 迭代器函数
i = i + 1
return a[i], t[a[i]] -- 返回键，值
end
end
这个工厂函数 pairsByKeys，首先将那些键，收集到一个数组中，然后对这个数组排序，最后返回那个迭代器函数。每个迭代步骤，迭代器都会按照数组 a 中的顺序，返回原始表中的下一个键与值。
有了这个函数，我们就可以轻松解决，一开始的那个，按顺序遍历表的问题了：
for name, line in pairsByKeys(lines) do
print(name, line)
end
与往常一样，所有的复杂性，都隐藏在迭代器中。
真正的迭代器
True Iterators
“迭代器” 这个名字，有点误导，因为我们的迭代器并不迭代：进行迭代的，是 for 循环。迭代器只为迭代，提供了连续的一些值。也许 “生成器，generator” 这个名字，会更好 -- 他为迭代 生成，generates 那些元素 -- 但 “迭代器” 这个名字，在其他语言（如 Java）中，已经被牢固确立。
不过，还有另一种构建迭代器的方法，其中迭代器会实际进行迭代。在使用这种迭代器时，我们不编写循环；相反，我们只需用一个描述迭代器在每次迭代时，必须要做的事情的参数，调用这种迭代器即可。更具体地说，这种迭代器会接收一个作为参数的函数，并在其循环内部，调用该函数。
作为一个具体的示例，我们来使用这种风格，再次重写那个 allwords 迭代器：
function allwords (f)
for line in io.lines() do
for word in string.gmatch(line, "%w+") do
f(word) -- 调用那个（作为参数的）函数
end
end
end
要使用这个迭代器，我们必须以一个函数的形式，提供其中的循环体。如果我们只打算打印出每个单词，则只需使用 print 即可：
allwords(print)
通常，我们使用一个匿名函数，作为主体。例如，下一段代码，会计算输入文件中，“hello" 一词出现的次数：
local count = 0
allwords(function (w)
if w == "hello" then count = count + 1 end
end)
print(count)
对于同一任务，用先前的迭代器样式编写，也没有很大的不同：
local count = 0
for w in allwords() do
if w == "hello" then count = count + 1 end
end
print(count)
真迭代器在旧版本的 Lua 语言中很流行，当时这门语言还没有 for 语句。与生成器式迭代器相比，他们有何不同呢？两种样式的迭代器，开销大致相同：每次迭代，都会调用一次函数。一方面，以真正的迭代器，编写迭代器会更容易（尽管我们可以使用协程，coroutines，来重获这种简便性，正如我们将在 “作为迭代器的协程” 小节中将看到的）。另一方面，生成器的样式会更加灵活。首先，他允许两个以上并行迭代。(例如，请设想对两个文件迭代，进行逐字比较的问题。）其次，他允许在迭代器主体内，使用 break 和 return 关键字。而在真正迭代器中，return 则是从匿名函数，而不是执行这个迭代的函数返回的。基于上述原因，总的来说，我（作者）通常会选用生成器。
练习
练习 18.1：请编写一个迭代器 fromto，使下面这个循环，等同于一个数字的 for 循环：
for i in fromto(n, m) do
-- body
end
可以将其实现为一个无状态迭代器吗？
练习 18.2：请给上一个练习中的迭代器，添加一个步长参数。咱们还能把他，作为无状态迭代器来实现吗？
练习 18.3：请编写一个，返回给定文件中不重复的所有单词的迭代器 uniquewords。(提示：以图 18.1，“遍历标准输入中所有单词的迭代器” 中的 allwords 代码开始；使用一个表来保存已报告的所有单词。）
练习 18.4：请编写一个返回给定字符串的所有非空子串的迭代器。
练习 18.5：请编写一个遍历给定集合的所有子集的真迭代器。(他可以使用同一个表，来处理其所有结果，而只在迭代之间改变这个表的内容，而不是为每个子集，都创建出一个新表。）