Iterator & Closure

迭代器和闭包

在Lua中，通常用函数表示迭代器，每次调用时返回集合的next元素，例如io.read()

闭包：可以访问自身环境中的局部变量，并能记住每次调用时的位置（状态）

一个闭包结构涉及两个函数：闭包本身 and 用于创建(return) 该闭包及封装变量的工厂函数


-- values就是这个工厂函数，t和i保存当前状态
function values(t)
	local i = 0  -- upvalue
	return function()
		i = i + 1
		return t[i]
	end
end	
	
t = {10, 20, 30}
for element in values(t) do
	print(element)
end

闭包的补充

闭包是Lua 中的一种特殊函数，它可以捕获并保存其外部环境的变量

内存占用

函数对象
外部变量：upvalue机制，闭包会捕获并保存外部环境的变量（工厂函数里的其他变量），会一直保存在内存中直到闭包被销毁（如上面values函数中的i）
额外数据结构：存储upvalue和函数上下文

运行时性能

闭包访问外部变量需要通过upvalue机制，慢于直接访问局部或全局变量
每次调用 有状态迭代器（如上）时，会创建一个新的闭包，略耗时一些

泛型for

保存三要素

迭代函数

不可变状态（如Lua表本身）

控制变量（表示当前状态，如下标）

形如

等价于

无状态迭代器

不用闭包，而是用 return（迭代函数、不可变状态、控制变量初始值）的方式来写迭代器工厂函数

要结束迭代则不返回值（等价于return nil），若返回nil后迭代器不会再继续迭代，但是初控制变量初始值可以为nil（这也是为什么下面forward list的迭代器能这么写）


-- e.g. 实现ipairs
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

next(t, k)：Lua的基本函数，随机返回t中下一个键值对


-- 实现pairs
function pairs (t) 
	return next, t, nil
end

-- 更直接的写法是，直接把返回值作为explist
for k, v in next, t do 
	-- loop body
end

practice: 单向链表的迭代器


List = {val = 0, next = nil}

function List:new(val, next)
    local node = {val = val, next = next}
    return node
end


local n1 = List:new(10, nil)
local n0 = List:new(2, n1)
local head = List:new(0, n0)


local function getnext (list, node)
		if not node then  
				return list
		else
				return node.next
		end
end

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

for node in traverse(head) do
    print(node.val)
end