下面寫一下怎么給generic***for?***寫迭代器。
## 1. 迭代器和閉包
在Lua中，迭代器用function表示，每次調用該function，都會返回集合中的next元素。
每個迭代器都要在連續的調用之間保存一些state，這樣才能知道進行到哪一步，下一步該從哪開始處理。在Lua中，閉包可以處理這個問題。閉包結構包含兩個function：一個是閉包本身，另一個是factory，用來創建閉包。下面是個簡單的示例：
~~~
function values(t)
local i = 0
return function () i = i + 1; return t[i] end
end
~~~
在上面的例子中，values是factory。每次調用factory，都會創建一個新的閉包（迭代器本身）。該閉包在變量t和i中保存state。每次調用這個迭代器，都會從t中返回next元素的值。返回最后一個元素后，它會返回nil，標志著迭代器結束。
可以將上面的迭代器用在***while?***中,但是用generic***for?***更簡單：
~~~
t = {10, 20, 30}
function value(t)
local i = 0
return function () i = i + 1; return t[i] end
end
iter = value(t)
while true do
local element = iter()
if element == nil then break end
print(element)
end
t = {1, 2, 3}
for element in value(t) do
print(element)
end
~~~
執行結果如下：
generic***for?***為迭代器循環過程在內部保存state，不需要iter變量；每次迭代都調用該迭代器，并在迭代器返回nil時停止循環。
下面是一個復雜點的例子，從當前輸入的文件中遍歷所有的word。遍歷過程中保存兩個值：當前行（變量line），當前位置（pos），***string.find?***函數從當前行中搜索一個word，用'%w+'匹配，在匹配到word后，將當前位置pos置于該word之后的第一個字符處，并返回該word。否則，迭代器讀入一個新行再重復上面的過程。如果沒有更多的行，返回nil，標志迭代結束。
~~~
function allwords ()
local line = io.read()
local pos = 1
print("allwords begin")
return function ()
while line do
local s, e = string.find(line, "%w+", pos)
if s then
pos = e + 1
print("return the word")
return string.sub(line, s, e)
else
print("read next line")
line = io.read()
pos = 1
end
end
print("return nil, iter end")
return nil
end
end
for word in allwords() do
print(word)
end
~~~
執行結果如下：
注意執行打印出來的一些信息，可以幫助了解腳本的執行過程。
## 2. Generic***for?***的語義
前面的例子有一個缺陷，每次都需要創建一個新的閉包來初始化一個新的循環。大多數情況下，這不是什么太大的開銷。但是，有時也是不能接受的。這時就需要用generic***for?***本身來保存迭代器狀態。
Generic***for?***會保存3個值：iterator function， invariant state，control variable。generic***for?***的語法如下：
~~~
for <var-list> in <exp-list> do
<body>
end
~~~
這里，var-list是一個或多個變量的名字，用逗號分隔，exp-list是一個或多個表達式，也用逗號分隔。通常exp-list只有一個元素，對iterator factory的調用。例如：
~~~
for k, v in pairs(t) do print(k, v) end
~~~
var-list是k，v， exp-list是pairs(t)。通常，var-list也只有一個變量，如下：
~~~
for line in io.lines() do
io.write(line, "\n")
end
~~~
var-list的第一個變量為control variable，它的值為nil時表示循環結束。
***for?***循環先計算in后面的表達式的值，這些表達式會產生3個值，就是上面寫的generic***for*?**需要保存的3個值：iterator function， invariant state，control variable 的初始值。跟多賦值語句一樣，只有最后一個表達式可以產生多個值；但是所有的表達式的結果最終被調整為3個，多的丟棄，少的補nil （當使用簡單的迭代器的時候，factory只返回iterator function，invariant state和control variable的值為nil）。
完成上面的初始化步驟后，***for***用invariant state和control variable作為參數來調用iterator function。然后***for***將iterator function返回的值賦值給var-list中的變量，如果返回的第一個值為nil，那么循環結束。否則，***for***執行循環體代碼并再次調用iteration function，重復上面的過程。
下面的偽代碼也許能幫助理解：
~~~
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
~~~
如果iterator function為*f* ，invariant state為*s* ， control variable的初始值為*a0*，control variable會如下循環：
*a1* =*f* (*s?*,*a0?*),*a2* =**f (*s?*,*a1?*), *a3* =*f* (*s?*,*a2?*), ....
直到ai為nil。
## 3. 無狀態迭代器
顧名思義，無狀態迭代器自身不會保存任何state。因此，我們可以在多次循環里面用同一個迭代器，避免了創建新閉包的開銷。
每次迭代，for 循環用兩個參數 invariant state 和 control variable 來調用 iterator 函數。ipairs 是個典型的此類迭代器：
~~~
a = {"one", "two", "three"}
for i, v in ipairs(a) do
print(i, v)
end
~~~
迭代器的state 是被遍歷的table ，當前的index 是 control variable 。ipairs 和 iterator 實現都比較簡單，下面是一個示例：
~~~
local 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
~~~
在for 循環中，Lua調用 ipairs(a) ，得到3個值： iter 函數為iterator ， a 為invariant state ， 0 是control variable 的初始值。 然后，Lua調用 iter(a，0)， 得到1， a[1] 。下一次迭代，調用 iter(a，1)， 得到 2， a[2]，直到第一個nil值，迭代結束。
pairs 函數跟上面的 ipairs 類似，只是iterator 函數為 next， 不是iter。next 是Lua中的一個基本函數：
~~~
function pairs (t)
return next, t, nil
end
~~~
next(t, k) 調用，k 是 table t 中的一個key ，返回兩個值，next key 和 t[next key]，next(t, nil)返回 table 中的第一對值。例如：
很多人比較喜歡直接用next ，而不是用pairs：
~~~
for k, v in next, t do
<loop body>
end
~~~
for 循環的exp-list會被調整為3個值，Lua會得到next，t，nil，跟調用pairs(t)得到的結果是一樣的。
下面是一個遍歷鏈表的例子，代碼有點繞，仔細想一下就會明白的。
~~~
local function getnext (list, node)
return not node and list or node.next
end
function traverse (list)
return getnext, list, nil
end
list = nil
for line in io.lines() do
list = {val = line, next = list}
end
for node in traverse(list) do
print(node.val)
end
~~~
## 4. 復合狀態的迭代器
很多時候，需要保存的state，除了 invariant state 和 control variable 還有別的。這種情況，用閉包是最簡單的方案。還有一個可選方案，用table，把所有需要保存的東西都打包到table 中，想保存什么就把什么打包到table 中。在循環過程中，盡管state 始終是同一個table，但是table中的數據可以在循環過程中更改。迭代器把所有需要的數據到封裝到table 中，所有就忽略了generic *for* 提供的第二個參數。
下面把allwords那個示例改寫了一下，來展示一下上面所說的用法
~~~
local iterator
function allwords()
local state = {line = io.read(), pos = 1}
return iterator, state
end
function iterator(state)
while state.line do
--search for next word
local s, e = string.find(state.line, "%w+", state.pos)
if s then
-- update next position (after this word)
state.pos = e + 1
return string.sub(state.line, s, e)
else
state.line = io.read()
state.pos = 1
end
end
return nil
end
for word in allwords() do
print(word)
end
~~~
運行結果示例如下：
我們應該盡可能的使用無狀態的迭代器，將所有的state都保存到*for* 循環的變量中。在開始新的循環的時候就不需要創建新的對象。當你的迭代器不適合上面說的table的情況時，應該用閉包。用閉包更簡潔優美，并且效率更高，因為：1. 創建閉包比創建table開銷要小。 2. 訪問非局部變量（閉包中）比訪問table的域要更快。 后面還會講講用*coroutines* 來實現迭代器，更強大，但是代價也更高。
## 5. 真正的迭代器
“迭代器”這個名字其實有點誤導，因為我們的“迭代器”根本不做迭代操作，真正去做迭代操作的是 for 循環。“迭代器”只是為迭代過程提供連續的值。可能更好的名字應該叫“生成器”。
不過，下面展示一種真正去做迭代操作的“迭代器”，再把allwords 重寫一次：
~~~
function allwords(f)
for line in io.lines() do
for word in string.gmatch(line, "%w+") do
f(word) -- call the function
end
end
end
allwords(print)
print("=============================")
local count = 0
allwords(function(w) if w == "hello" then count = count + 1 end end)
print("the number of 'hello' is " .. count)
~~~
示例中 的參數f 可以傳相關的函數，示例中簡單的用了*print* 來顯示了一下句子中的word，用了一個匿名函數統計句子中的“hello”個數。
執行結果如下：
這種形式的迭代器在舊版本的Lua中很流行，那是Lua沒有*for* 語句。跟“生成器”形式的迭代器比起來，到底哪一種好呢？兩種開銷差不多，每次迭代都是一次函數調用。從一方面講，這種舊式迭代器，更容易寫。但是“生成器”形式的迭代器更靈活。首先，她可以同時進行兩個平行的迭代（例如，比較兩個句子中的word，一個一個的比），另外，可以用*break* 在迭代過程中退出。總的來說，“生成器”形式的迭代器也許更受歡迎一點。
水平有限，如果有朋友發現錯誤，歡迎留言交流。
