迭代器与通用的 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 所创建出的,其外部变量 ti 中。每次我们调用该迭代器时,他都会从列表 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) 等值,直到 ainil。如果 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 循环会将其表达式列表,调整为三个结果,从而他会得到 nexttnil;这正是他在调用 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,来重获这种简便性,正如我们将在 “作为迭代器的协程” 小节中将看到的)。另一方面,生成器的样式会更加灵活。首先,他允许两个以上并行迭代。(例如,请设想对两个文件迭代,进行逐字比较的问题。)其次,他允许在迭代器主体内,使用 breakreturn 关键字。而在真正迭代器中,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:请编写一个遍历给定集合的所有子集的真迭代器。(他可以使用同一个表,来处理其所有结果,而只在迭代之间改变这个表的内容,而不是为每个子集,都创建出一个新表。)

Last change: 2024-07-23, commit: 1e691f0