Lua迭代器和泛型for

迭代器是一种可以让我们遍历一个集合中所有元素的代码结构。在Lua语言中，通常使用函数表示迭代器：每一次调用函数时，函数会返回集合中的”下一个“元素。一个典型的例子是io.read，每次调用该函数时它都会返回标准输入中的下一行，在没有读取的行时返回nil。

所有的迭代器都需要在连续的调用之间保存一些状态，这样才能知道当前迭代所处的位置及如何从当前位置步进到下一位置。对于函数io.read而言，C语言会将状态保存在流的结构体中。对于我们自己的迭代器而言，闭包则为保存状态提供了一种良好的机制。庆祝，一个闭包就是一个可以访问其自身的环境中一个或多个局部变量的函数。这些变量将连续调用过程中的值并将其保存在闭包中，从而使得闭包能够记住迭代所处的位置。当然，要创建一个新的闭包，我们还必须创建非局部变量。因此，一个闭包结构通常涉及两个函数；闭包本身和一个用于创建该闭包及其封装变量的工程。
作为示例，让我们来为列表编写一个简单的迭代器。与ipairs不同的是，该迭代器并不是返回每个元素的索引而是返回元素的值：

1
2
3
4
function values(t)
	local i = 0
	return function () i = i +1 ；return t[i] end
end

在这个例子中，values就是工厂。每当调用这个工厂时，它就会创建一个新的闭包（既迭代器本身）。这个闭包将它的状态保存在其外部的变量t和i中，这两个变量也是由values创建的。每次调用这个迭代器时，它就从列表t中返回下一个值。在遍历完最后一个元素后，迭代器返回nil，表示迭代结束。
我们可以在一个while循环中使用这个迭代器：
1
2
3
4
5
6
7
t = {10,20,30}
iter = values(t)
while true do
	local element = iter()
	if element == nil then break end
	print(element)
end

不过，使用泛型for更简单。毕竟，泛型for正是为了这种迭代而设计的：
1
2
3
4
t = {10,20,30}
for element in values(t) do
	print(element)
end

泛型for为一次迭代循环做了所有的记录工作：它的内部保存了迭代函数，因此不需要变量iter；它在每次做新的迭代时都会再次调用迭代器，并在迭代器返回nil时结束循环。
下面是一个更高级的示例，它可以遍历来自标准输入的所有单词。

示例 遍历来自标准输入的所有单词的迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function allwords()
	local line = io.read()		-- 当前行
	local pos  = 1				-- 当前行的当前位置
	return function()			-- 迭代函数
	while line do 				-- 当还有行时循环
		local w , 3 = string.match(line,"(%w+)()",pos)
			if w then				-- 发现一个单词？
				pos = e 			-- 下一个位置位于该单词后
				return w 			-- 返回该单词
			else
				line = io.read()	-- 没找到单词；尝试下一行
				pos  = 1			-- 从第一个位置重新开始
			end
		end
		return nil					-- 没有行了：迭代结束
	end
end

为了完成这样的便利，我们需要保存两个值：当前行的内容及当前行的当前位置。有了这些数据，我们就可以不断产生下一个单词。这个迭代函数的主要部分是调用函数string.match，以当前位置作为起始在当前行中搜索一个单词。函数string.match使用模式’%w+’来匹配一个“单词”，也就是匹配一个或多个字母/数字字符。如果函数string.match找到了一个单词，它就捕获并返回这个单词及该单词之后的第一个字符位置，迭代函数则更新当前位置并返回该单词；否则，迭代函数读取新的一行，然后重复上述搜索过程。在所有的行都被读取完后，迭代函数返回nil以表示迭代结束。
尽管迭代器本身有点复杂，但allwords的使用还是很简明易懂的：

1
2
3
for word in allowrds () do
	print(word)
end

对于迭代器而言，一种常见的情况就是，编写迭代器可能不太容易，但使用迭代器却十分简单。这也不是一个大问题，因为使用Lua语言编程的最终用户一般不会去定义迭代器，而只会使用那些宿主应用已经提供的迭代器。

泛型for的语法

上述那些迭代器都有一个缺点，即需要为每个新的循环创建一个新的闭包。对于大多数情况而言，这或许不会有什么问题。例如，在之前的allwords迭代器中，创建一个闭包的开销相对于读取整个文件的开销而言几乎可以忽略不计。但是，在另外一些情况下，这样的开销可能会很可观。在这类情况中，我们可以通过使用泛型for自己保存迭代状态。
泛型for在循环过程中在其内部保存了迭代函数。实际上，泛型for保存了三个值：一个迭代函数、一个不可变状态和一个控制变量。

1
2
3
for var-list in exp-list do
	body
end

其中，var-list是由一个或多个变量名组成的列表，以逗号分隔；exp-list是一个或多个表达式组成的列表，同样以逗号分隔。通常，表达式列表只有一个元素，即一句对迭代器工厂的调用。例如，在如下代码中，变量列表是k,v,表达式列表只要一个元素pairs(t):
1
for k,v in pairs(t) do print(k,v) end

我们把变量列表的第一个（或唯一的）变量称为控制变量，其值在循环过程中永远不会是nil，因为当其值为nil时循环就结束了。
for做的第一件事情就是对in后面的表达式求值。这些表达式应该返回三个值供for保存：迭代函数、不可变状态和控制变量的初始值。类似于多重赋值，只有最后一个表达式能够产生不止一个值；表达式列表的结果值会保留三个，多余的值会被丢弃，不足三个则以nil补齐。例如，在使用简单迭器时，工厂只会返回迭代函数，因此不可变状态和控制变量都是nil。
在上述的初始化步骤完成后，for使用不可变状态和控制变量为参数来调用迭代函数。从for代码结构的立足点来看，不可变状态根本没有意义。for只是把从初始化步骤得到的状态值传递给所有迭代函数。然后，for将迭代函数的返回值赋给变量列表中声名的变量。如果第一个返回值为nil，那么循环终止；否则，for执行它的循环体并再次调用迭代函数，再不断地重复这个过程。
更确切地说，形如
1
for var_1,... ,var_n in explist do block end

这样代码结构与下列代码等价：
1
2
3
4
5
6
7
8
9
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后得到额外的返回值。

无状态迭代器

顾名思义，无状态迭代器就是一种自身不保存任何状态的迭代器。因此，可以在多个循环中使用同一个无状态迭代器，从而避免创建新闭包的开销。
正如刚刚所看到的，for循环会以不可变状态和控制变量为参数低啊用迭代函数。一个无状态迭代器只根据这两个值来迭代生成下一个元素。这类迭代器的一个典型例子就是ipairs，它可以迭代一个序列中的所有元素：

1
2
3
4
a = {"one","two","three"}
for i,v in ipairs(a) do
	print(i,v)
end

迭代的状态由正在被遍历的表（一个不可变状态，它不会在循环中改变）及当前的索引值（控制变量）组成。ipairs和迭代器都非常简单，我们可以在Lua语言中将其编写出来：
1
2
3
4
5
6
7
8
9
10
11
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

当调用for循环中的ipairs(t)时，ipairs(t)会返回三个值，即迭代函数iter、不可变状态表t和控制变量的初始值0。然后，Lua语言调用iter(t,0)，得到1,t[1]（除非t[1]已经变成nil）。在第二次迭代中，Lua语言调用iter(t,1)，得到2,t[2]，依次类推，直至得到第一个为nil的元素。
函数pairs与函数ipairs类似，也用于遍历一个表中的所有元素。不同的是，函数pairs的迭代函数是Lua语言中的一个基本函数next：
1
2
3
function pairs(t)
	return next,t,nil
end

在低啊用next(t,k)时，k是表t的一个键，该函数会以随机次序返回表中的下一个键及k对应的值（作为第二个返回值）。调用next(t,nil)时，返回表中的第一个键值对。当所有元素被遍历完时，函数next返回nil。
我们可以不调用pairs而直接使用next：
1
2
3
for k,v in next , t do
	loop body
end

请注意，for循环会把表达式列表的结果调整为三个值，因此上例得到的是next、t和nil，这也正与pairs(t)的返回值完全一致。
关于无状态迭代器的另一个有趣的示例是遍历链表的迭代器（链表在Lua语言中并不常见，但有时也需要用到）。我们的第一反应可能是只把当前节点当做控制变量，以便于迭代函数能够返回下一个节点：
1
2
3
4
5
6
7
local function getnext(node)
	return node.next
end

function traverse(list)
	return getnext, nil, list
end

但是，这种实现会跳过第一个节点。所以，我们需要使用如下的代码：
1
2
3
4
5
6
7
8
9
10
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

这里的技巧是，除了将当前节点作为控制变量，还要将头节点作为不可变状态。第一次调用迭代函数getnext时，node为nil，因此函数返回list作为第一个节点。在后续的调用中，node不再是nil，所以迭代函数会像我们所期望的那样返回node.next。

按顺序遍历表

一个常见的困惑发生在开发人员想要对表中的元素进行排序时。由于一个表中的元素没有顺序，所以如果想对这些元素排序，就不得不把键值对拷贝到一个数组中，然后再对数组进行排序。
假设我们要读取一个源文件，然后构造一个表来保存每个函数的名称及其声明所在的行数，形式如下：

1
2
3
4
5
lines = {
	["luaH_set"]     = 10,
	["luaH_get"]	 = 24,
	["luaH_present"] = 48,
}

现在，我们想按照字母顺序输出这些函数名。如果使用pairs遍历表，那么函数名会按照随机的顺序出现。由于这些函数名是表的键，所以我们无法直接对其进行排序。不过，我们把他们放到数组中，那么就可以对它们进行排序了。首先，我们必须创建一个包含函数名的数组，然后对其排序，再最终输出结果。
1
2
3
4
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等来实现有序，然而后者使用则是天然的随机顺序（虽然大多数情况下顺序随机也无碍，但有时可能并非我们想要的）。
现在，我们已经准备好写一个按照键的顺序来遍历表的迭代器了：
1
2
3
4
5
6
7
8
9
10
11
12
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
		returna[i],t[a[i]]		--返回键和值
	end
end

工厂函数pairsByKeys首先把键放到一个数组中，然后对数组进行排序，最后返回迭代函数。在每一步中，迭代器都会按照数组a中的顺序返回原始表中的下一个键值对。可选的参数f允许指定一种其他的排序方法。
使用这个函数，可以很容易地解决开始时提出的按顺序遍历表的问题：
1
2
3
for name,line in pairsByKeys(lines) do 
	print(name,line)
end

像通常的情况一样，所有的复杂性都被隐藏到了迭代器中。

迭代器的真实含义

“迭代器”这个名称多少有点误导性，这是因为迭代器并没有进行实际的迭代：真正的迭代时for循环完成的，迭代器只不过为每次的迭代提供连续的值。或许，称其为“生成器”更好，表示迭代生产元素；不过，“迭代器”这个名字已在出入Java等其他语言中被广泛是用了。
然而，还有一种创建迭代器的方式可以让迭代器进行实际的迭代操作。当使用这种迭代器时，就不再需要编写循环了。相反，只需要调用这个迭代器，并传入一个描述了在每次迭代时需要做什么的参数即可。更确切地说，迭代器接收了一个函数作为参数，这个函数在循环的内部被调用，这种迭代器就被称为真正的迭代器。
  举一个具体的例子，让我们使用这种风格再次重写allowrds迭代器：

1
2
3
4
5
6
7
function allwords(f)
	for line in io.line() do
		for word in string.gmatch(line,"%w+") do
			f(word)			--调用函数
		end
	end
end

使用这个迭代器时，我们必须传入一个函数作为循环体。如果我们只想输出每个单词，那么简单地使用函数print即可：
1
allwords(print)

通常，我们可以使用一个匿名函数作为循环体。例如，以下的代码用于计算单词”hello”在输入文件中出现的次数：
1
2
3
4
5
local count = 0
allwords(function(w)
	if w == "hello" then count = count + 1 end
end)
print(count)

同样的需求，如果采用之前的迭代器风格，差异也不是特别大：
1
2
3
4
5
local count = 0
for w in allwords() do
	if w == "hello" then count = count + 1 end
end
print(count)

    真正的迭代器在老版本的Lua语言中曾非常流行，那是还没有for语句。真正的迭代器与生成器风格的迭代器相比怎么样呢？这两种风格都有大致相同的开销，即每次迭代都有一次函数调用。一方面，编写真正的迭代器比较容易。另一方面，生成器风格的迭代器则更灵活。首先，生成器风格的迭代器允许两个或更多个并行的迭代。其次，生成器风格的迭代器允许在循环体中使用break和return语句。使用真正的迭代器，return语句从匿名函数中返回而非从进行迭代的函数中返回。