目标：利用泛型for写出高效迭代器
迭代器是一种支持指针类型的结构，可以便利集合中的每个元素。在Lua中常使用函数来描述迭代器，每次调用会返回集合中的下一个元素。
迭代器需要保留上一次成功调用的状态和下一次成功调用的状态，也就是说必须知道它来自哪里和将要前往哪里。闭包提供的机制可以很容易实现这个任务。
闭包是一个内部函数，闭包可以访问一个或多个外部函数的外部局部变量。每次闭包的成功调用后，这些外部局部变量都保存他们的值（状态）。如果要创建一个闭包必须要创建其外部局部变量，所以典型的闭包的结构包含两个函数：闭包自身、创建闭包的工厂函数。
迭代器（Iterator）是一种可以遍历集合中所有元素的机制。在Lua中，迭代器表示为函数，每调用一次函数即返回集合中下一个元素。每个迭代器都需要在每次成功调用之间保持一些状态，这样才能知道当前所在位置以及如何步进到下一个位置，闭包（closure）对此类任务提供了极佳的支持。
闭包
理解闭包之前，必须理清Lua中的函数：
- Lua中函数是“第一类值”，意味着Lua中的函数与基本数据类型的值（数值、字符串、布尔值）具有相同的权力。
- 函数具有特定的词法域，即一个函数可以嵌套在另一个函数中，内部函数可以访问外部函数中的局部变量。
- 函数可以存储到变量（全局变量或局部变量）或
table中，也可以作为实参传递给其他函数，还可以作为其他函数的返回值。
闭包（closure）是一种可以访问其外部嵌套环境中的局部变量的函数。对于闭包而言，函数中的局部变量可用于在成功调用之间保持状态值，从而使闭包可以记住遍历时所处的环境和位置。为了创建闭包必须创建它的"非局部变量（non-local variable，upvalue）"，因此闭包结构通常涉及两个函数：闭包本身、用于创建闭包的工厂函数。
示例：迭代器之返回元素的值
-- 迭代器：返回元素的值
function values(tbl)
local i = 0
return function()
i = i + 1
return tbl[i]
end
end
-- test
local tbl = {1, 2, 3, 4, 5}
-- 创建迭代器
local iterator = values(tbl)
while true do
-- 调用迭代器
local ele = iterator()
if ele==nil then
break
end
print(ele)
end
解析：values本身是一个工厂，每当调用工厂时会创建新的闭包即迭代器本身，闭包函数将其状态保存在外部变量tbl和i中。每当调用迭代器时会从列表tbl中返回下一个值，直到最后一个元素返回后，迭代器返回nil表示结束。
Lua通过闭包（closure）来处理内部函数访问“非局部变量（upvalue）”，一个闭包其实就是一个函数加上该函数所需访问的所有“非局部变量（upvalue）”。
示例：递归之斐波拉契数列
-- 根据索引获取对应位置中斐波那契数列的值
function fibonacci(index)
if index>0 and index<=2 then
return 1
else
return fibonacci(index-1) + fibonacci(index-2)
end
end
-- 打印连续10个斐波那契数列数值
local i = 1
while i<=10 do
print(i, fibonacci(i))
i = i + 1
end
示例：递归阶乘
local fact
fact = function(n)
if n==0 then
return 1
else
-- 调用fact时，fact必须先定义，而非此函数自身。
return n*fact(n-1)
end
end
-- TEST
print(fact(4)) -- 24
-- 简化形式
local function fact(n)
if n==0 then
return 1
else
return n*fact(n-1)
end
end
-- TEST
print(fact(4)) -- 24
示例：创建遍历当前文件中所有单词的迭代器
为了遍历当前文件中所有单词，需要保存两个值：当前行的内容、当前行所处的位置。有了这些信息就可以不断地产生下一个单词。
-- 迭代器
function iterator()
-- 获取当前行
local line = io.read()
-- 当前位置
local pos = 1
-- 迭代器函数
return function()
-- 遍历有效行
while line do
-- 获取单词起止下标
local begin_index, end_index = string.find(line, "%w+", pos)
if begin_index then
pos = end_index + 1
-- 返回单词
return string.sub(line, begin_index, end_index)
else
-- 进入下一行
line = io.read()
pos = 1
end
end
return nil
end
end
-- 遍历
for item in iterator() do
print(item)
end
$ lua
> dofile("test.lua")
this is a demo
this
is
a
demo
使用闭包实现时存在一个缺点，就是他需要为每个新的循环都创建一个新的闭包。对于大多数情况而言，这也许并不会有什么问题。
泛型for
泛型for正是为迭代而设计的，泛型for为一次迭代循环做了所有的记录，其内部保存了迭代器函数，因此无需iterator变量。并且在每次新迭代时调用迭代器，并在迭代器返回nil时结束循环。
-- 迭代器：返回元素的值
function values(tbl)
local i = 0
return function()
i = i + 1
return tbl[i]
end
end
-- test
local tbl = {1, 2, 3, 4, 5}
-- 泛型for
for ele in values(tbl) do
print(ele)
end
泛型for在循环遍历过程中，其内部保存了迭代器函数，而实际上是保存着3个值：迭代器函数、恒定状态、控制变量。
--[[
var-list 是一个或多个变量名的列表，以逗号分隔
exp-list 是一个或多个表达式的列表，以逗号分隔。
通常表达式列表只有一个元素，即对迭代器函数的调用。
--]]
for <var-list> in <exp-list> do
<body>
end
-- eg
for k,v in pairs(tbl) do
print(k,v)
end
for i,v in ipairs(arr) do
print(i, v)
end
--[[
值得注意的是，pairs()和ipairs()并非是迭代器，而只是一个表达式。
表达式用于产生3个参数，真正的迭代器是表达式内部返回的用于查询下一个元素的函数。
--]]
for做的第一件事情就是对in后面的表达式求值，这些表达式应该返回3个值供for保存：迭代器函数、恒定状态、控制变量的初值。这里和多重赋值一样，只有最后一个表达式才会产生多个结果，并且只会保留前3个值，多余的值会被丢弃，如果不够的话，则以nil补足。
- 在初始化完成后，
for会以恒定状态和控制变量来调用迭代器函数。 - 然后
for将迭代器函数的返回值赋予变量列表中的变量，如果第一个返回值为nil那么循环就终止。否则，for执行其循环体。 - 随后再次调用迭代器函数，并重复这个过程。
泛型for中的pairs和ipairs有什么异同点呢？
-
ipairs用于迭代数组且不能返回nil，若遇到nil则退出。 -
pairs用于迭代表，可遍历表的键名，且可以返回nil。
无状态迭代器
无状态迭代器是指自身不保存任何状态的迭代器，可在多个循环中使用同一个无状态迭代器，避免创建的新的闭包的开销。
在每次迭代中for循环都会用恒定状态和控制变量来调用迭代器函数，一个无状态的迭代器可根据这两个值来为下次迭代生成下一个元素。此类迭代器典型的例子就是ipairs，它可以用来迭代一个数组中所有的元素。
for i,v in ipairs(arr) do
print(i,v)
end
这里迭代状态就是需要遍历的table（恒定状态，不会在循环中改变）以及当前索引值（控制变量）。ipairs用于创建迭代器的工厂函数和迭代器都很简单。
-- 迭代器
local function iterator(array, index)
index = index + 1
local value = array[index]
if value then
return index, value
end
end
-- 创建迭代器的工厂函数
function ivpair(array)
return iterator, array, 0
end
-- 泛型for
local arr = {10, 20, 30}
for i,v in ivpair(arr) do
print(i,v)
end
- 当Lua调用
for循环的ipair时会获得3个值：迭代器函数iterator、恒定状态arr、控制变量index的初始值0。 - 然后Lua调用迭代器
iterator(arr, 0)得到1,arr[1]。 - 类此类推，继续调用迭代器，直到第一个
nil元素为止。
函数pairs也是用于遍历一个table中的所有元素，不同之处在于，pairs的迭代器函数是一个基础函数next。
-- 创建迭代器的工厂函数
function kvpair(tbl)
-- 迭代器为next
return next, tbl, nil
end
-- 泛型for
local tbl = {nickname="alice", gender=1}
for k,v in kvpair(tbl) do
print(k,v)
end
Lua在调用next(table, key)时，key是table种的一个key，next调用会以table中的任意次序返回一组值：此table的下一个key以及这个key所对应的值。而调用next(table, nil)时，返回table的第一组值。若没有下一组值时，next会返回nil。
可以不通过pairs调用而直接使用next
local tbl = {nickname = "alice", gender = 1}
for k,v in next,tbl do
print(k,v)
end
for循环
Lua中的for循环分为2种数值型、泛型，其中泛型又分为有状态和无状态。
数值型for
需要注意的是在数值型for中的初始值、步长、终止值的计算仅仅在最开始第一次循环就保存起来了，也就是说在数值for循环中即使对控制变量做了修改也不会影响循环的过程，这一点和C语言的循环是不同的。
local arr = {10, 20, 30}
for i,v in ipairs(arr) do
arr = nil -- for循环中的起始值、步长、终止值的计算只在最开始计算一次就保存起来了
print(i,v)
end
-- 循环变量i和v是for循环的局部变量，跳出for循环后局部变量就会被销毁。
print(i,v) -- nil nil
泛型for
泛型循环有3个重要参数：迭代器、初始状态、初始状态输入，这种for循环如同一个有限状态机，只要给定状态转移函数、初始状态、初始状态输入就可以自动运行下去，不停的产生出下一个状态。那么循环怎么还有一个状态呢？这个状态到底是个什么东西呢？
循环的目的是为了遍历，而遍历的目的却是为了寻找下一个值。
在C语言中for循环遍历线性结构的对象
for(int i=0; i<size; i++){
//...
}
但是对于非线性结构，要遍历就没有那么简单，是不可以直接使用++来查询下一个元素的。
而在C++中的如STL的一些容器和Lua中的table，遍历时都会使用到迭代器（Iterator），虽然形式不同，但本质上无论C++的迭代器、Lua的迭代函数或是树、图的遍历算法，都是一个有限状态机，为的是查找下一个元素。
