8. 列表
这一章你会学到:
- 为什么需要一个装很多值的容器;
- 列表字面量,按下标读和写;
append、size、insert、remove、removeAt、clear等常用方法;- 下标越界在运行时会怎样;
- 为什么空列表字面量要写类型;
List和MutableList的关系:只读视角、快照和复制;- 两个列表怎么比较、怎么排序;
@std/lists.spr里不需要函数值的那部分工具。
8.1 为什么需要列表
一个学生的成绩,存一个变量就够了:
let score_ada = 90
let score_bob = 7240 个学生呢?你不想起 40 个变量名。列表把一串同类型的值装在一起,用一个名字拿着:
let scores = [90, 72, 85]
print(scores)
print(scores.size())
print(scores[0])
print(scores[2])
print(scores[0] + scores[2])
scores[0] = 60
scores.append(100)
print(scores)[90, 72, 85]
3
90
85
175
[60, 72, 85, 100]逐行读这个程序:
let scores = [90, 72, 85]:[...]是列表字面量,元素用逗号隔开。没写类型时,它是MutableList[Int],元素类型从内容推断成Int。print(scores)打印[90, 72, 85]:方括号和逗号是列表的打印格式。如果元素是字符串,打印时不带引号。scores.size()是元素个数。size是方法,要点号调用、带括号。scores[0]是第一个元素,下标从 0 开始;所以scores[2]是第三个元素85。scores[0] + scores[2]把两个元素当普通Int相加,得到175。scores[0] = 60改写第一个元素。scores.append(100)在末尾追加一个元素。append没有返回值,所以不能写print(scores.append(100))。
读和写各有两副写法,效果一样:scores[0] 等于 scores.get(0),scores[0] = 60 等于 scores.set(0, 60)。
8.2 一批常用方法
往列表里放东西和拿东西之外,还要问"在不在"、"是第几个"、删除元素:
let names = ["Ada", "Bob", "Cyd"]
print(names.contains("Bob"))
print("Cyd" in names)
print(names.indexOf("Bob"))
print(names.indexOf("Zoe"))
print(names.isEmpty())
names.insert(1, "Eve")
print(names)
print(names.remove("Ada"))
print(names)
print(names.removeAt(0))
print(names)
print(names.get(0))
print(names.size())
names.clear()
print(names)
print(names.isEmpty())true
true
1
-1
false
[Ada, Eve, Bob, Cyd]
true
[Eve, Bob, Cyd]
Eve
[Bob, Cyd]
Bob
2
[]
true逐行读:
names.contains("Bob")问列表里有没有等于"Bob"的元素,"Cyd" in names是同一件事的另一种写法。names.indexOf("Bob")是它的位置,从 0 数;names.indexOf("Zoe")找不到,得到-1。names.isEmpty()问列表是不是空的;这里还有元素,所以false。names.insert(1, "Eve")在下标 1 的位置插入,原来的"Bob"、"Cyd"往后挪一格。names.remove("Ada")按值删除第一个等于"Ada"的元素,返回Bool表示有没有删到;删除后是[Eve, Bob, Cyd]。names.removeAt(0)按下标删除,返回被删掉的那个元素"Eve";列表变成[Bob, Cyd]。names.get(0)就是names[0],得到"Bob";names.size()是 2。names.clear()清空列表,打印成[];isEmpty()这才变成true。
常用方法一张表(都在可改列表 MutableList 上):
| 方法 | 作用 |
|---|---|
size() / isEmpty() | 元素个数 / 是否为空 |
get(i) / xs[i] | 读下标 i |
set(i, x) / xs[i] = x | 写下标 i |
append(x) | 末尾追加 |
insert(i, x) | 在下标 i 处插入 |
remove(x) | 按值删除第一个,返回 Bool |
removeAt(i) | 按下标删除,返回被删的元素 |
contains(x) / x in xs | 是否含有 |
indexOf(x) | 第一个位置,没有是 -1 |
clear() | 清空 |
sort() | 就地升序排序 |
8.3 用循环处理列表
实际程序很少只处理一个元素,而是把列表过一遍。下面的程序同时做累加和变换,请对照追踪表读:
let numbers = [4, 1, 3]
var total = 0
let doubled: MutableList[Int] = []
for n in numbers:
total += n
doubled.append(n * 2)
print(total)
print(doubled)
for i in range(0, numbers.size()):
print(i.toString() + ": " + numbers[i].toString())8
[8, 2, 6]
0: 4
1: 1
2: 3第一个循环每次拿到一个元素 n,做两件事:把 n 加到 total,把 n * 2 追加到 doubled。跟着值走:
| 第几步 | n | total | doubled |
|---|---|---|---|
| 开始 | — | 0 | [] |
| 1 | 4 | 4 | [8] |
| 2 | 1 | 5 | [8, 2] |
| 3 | 3 | 8 | [8, 2, 6] |
输出 8 和 [8, 2, 6] 就是循环结束时的 total 和 doubled。
let doubled: MutableList[Int] = []先建一个空列表接结果。空字面量必须写元素类型,8.5 会看到不写会怎样。total += n是total = total + n的简写。total必须声明成var才能改。- 第二个循环用
range(0, numbers.size())生成下标0, 1, 2;i是Int。 i.toString()把Int变成String,再和别的字符串拼接。直接拼也行:"n=" + i会得到n=2,+遇到字符串就做拼接;i.toString()只是把"这里要文本"写得更明确。
8.4 下标越界的后果
下标必须落在 0 到 size() - 1 之间。超出范围不是编译错误:编译器不知道运行时列表有多长。它是运行时错误。
把 ch08_oob.spr 的内容存成 main.spr 再运行:
sprig run main.sprSPR-RUNTIME-EXCEPTION [RUNTIME] main.spr:2:1: List index 5 is out of bounds; size is 3
hint: Check the list length before indexing. Run with --stacktrace to see the JVM stack.
1 error(s); run 'sprig explain <code>' for details on a diagnostic code.程序在这里停下,以非零状态退出,后面的语句不会执行。读法:错误码 SPR-RUNTIME-EXCEPTION、位置 main.spr:2:1、"下标 5 越界,长度是 3",然后 hint 告诉你先检查长度再取下标。这类错误是你程序的 bug,正确的做法是让下标不越界,而不是"接住"它。
学过其他语言?
很多语言越界会给出 IndexOutOfBoundsException/IndexError 之类的原始异常。Sprig 把它翻译成一条带错误码和提示的诊断,程序同样会停。下标从 0 开始、结束下标不含(range(0, xs.size()) 正好覆盖所有下标)和 Python 一致,和 Java 的数组一致。
8.5 空列表字面量要写类型(故意写错)
下面这段通不过检查:
let xs = []
print(xs)SPR-TYPE-INFER [TYPE] main.spr:1:10: Cannot infer the type of an empty list literal; add a type annotation[] 里一个元素都没有,编译器没有线索判断元素是什么类型,所以要求你写出来:
let a: MutableList[Int] = [] # 以后要 append、set
let b: List[String] = [] # 只读写了类型,之后往里放东西时元素类型就受检查;放错类型会得到类型错误,而不是运行时惊喜。
8.6 List 和 MutableList
Sprig 把"能改"和"不能改"写进类型:MutableList[T] 可改,List[T] 只读。很多函数只需要读,就在签名上写 List,向调用者承诺"我不会改你的列表"。MutableList 可以当 List 传——同一份数据,只是对方拿到只读视角。
# MutableList 可以传给要 List 的函数:对方看到的是同一个列表的只读视角。
func total(xs: List[Int]) -> Int:
var sum = 0
for x in xs:
sum += x
return sum
let numbers = [1, 2, 3]
print(total(numbers))
numbers.append(4)
print(total(numbers))
let snapshot = numbers.toList()
numbers.append(5)
print(snapshot.size())
print(numbers.size())6
10
4
5逐行读:
func total(xs: List[Int])遍历求和。调用者手里的numbers是MutableList,直接传进去,不用复制。- 前两行 6 和 10:
numbers.append(4)之后total(numbers)从 6 变成 10,说明函数看到的就是调用者那个列表。 let snapshot = numbers.toList()做一份只读快照;随后numbers.append(5),快照还是 4 个元素,原列表是 5 个。
toList() 和 toMutableList() 的复制行为值得单独记。看这个程序:
let grades = [90, 72]
let view: List[Int] = grades
grades.append(85)
print(view)
let snapshot = grades.toList()
grades.append(60)
print(snapshot)
print(grades)
let frozen: List[Int] = [1, 2]
let copy = frozen.toMutableList()
copy.append(3)
print(frozen)
print(copy)
let same = grades.toMutableList()
same.append(100)
print(grades)
print(same)[90, 72, 85]
[90, 72, 85]
[90, 72, 85, 60]
[1, 2]
[1, 2, 3]
[90, 72, 85, 60, 100]
[90, 72, 85, 60, 100]对照输出的七行:
let view: List[Int] = grades是只读视角,同一份数据。grades.append(85)之后view里也有 85(第 1 行)。toList()复制一份只读快照。之后grades.append(60),快照还是三个元素(第 2 行),原列表四个(第 3 行)。let frozen: List[Int] = [1, 2]是只读列表;frozen.toMutableList()复制出可改副本copy。改copy不影响frozen(第 4、5 行)。grades.toMutableList():grades本来就是可改的,所以不复制,返回的是同一个列表(第 6、7 行都多了 100)。toMutableList()只在只读列表上才是"复制"。
学过其他语言?
List 不是 Java 的 Collections.unmodifiableList 包装,也不是把数据冻住:它只是同一个集合的只读视角,元素本身(如果元素是可改的集合)不受保护。要独立的一份,用 toList() 快照或 toMutableList() 复制。
故意写错:改只读列表
let xs: List[Int] = [1, 2]
xs.append(3)SPR-COLLECTION-IMMUTABLE [TYPE] main.spr:2:1: Cannot call mutating method 'append' on an immutable collection; take an explicit snapshot with toMutableList()append、set、insert、remove、removeAt、clear、sort 这些改内容的方法只存在于 MutableList。变量是 List 时用它们,编译器直接拒绝,并提示用 toMutableList() 换成可改的。
8.7 比较和排序
列表可以用 == 比较内容,用 sort() 排序:
let a = [1, 2, 3]
let b = [1, 2, 3]
let c = [3, 1]
print(a == b)
print(a == c)
print(a != c)
let words = ["pear", "fig", "banana"]
words.sort()
print(words)
let scores = [90, 72, 85]
scores.sort()
print(scores)true
false
true
[banana, fig, pear]
[72, 85, 90]a == b为true:两个列表长度相同,每个位置的元素按==相等。a == c为false:元素一样但顺序不同,也不相等。列表比较看内容,不看是不是同一个列表。words.sort()就地按升序排好字符串,打印得到[banana, fig, pear]。sort()没有返回值,所以它自己单独占一行,不能写进print。数字列表同理。
8.8 @std/lists:不用函数值的工具
内置方法有意保持少;批量操作放在标准库模块 @std/lists.spr 里:
import "@std/lists.spr" as lists
# 想不改动调用者的列表,就先 toList() 做只读快照再传给 lists.sorted。
let words = ["pear", "fig", "banana", "fig"]
print(lists.sorted(words.toList()))
print(words)
print(lists.reversed(words))
print(lists.distinct(words))
print(lists.index_of(words, "fig"))
print(lists.sum([1, 2, 3]))
print(lists.take(words, 2))
print(lists.drop(words, 3))[banana, fig, fig, pear]
[pear, fig, banana, fig]
[fig, banana, fig, pear]
[pear, fig, banana]
1
6
[pear, fig]
[fig]import "@std/lists.spr" as lists导入模块,之后用lists.函数名调用。lists.sorted(words.toList())返回排好序的新列表,原来的words不变(第 2 行还是原顺序)。这里先toList()做只读快照:把一个可改列表直接传给lists.sorted,当前实现会连原列表一起排序(模块注释说不会改输入,这是实现和注释不一致的地方)。lists.reversed(words)返回倒序的新列表,lists.distinct(words)每个值只保留第一次出现的位置。lists.index_of(words, "fig")是"fig"第一次出现的下标;lists.sum([1, 2, 3])是求和。lists.take(words, 2)取前两个,lists.drop(words, 3)丢掉前三个。- 这里选的是不需要函数值的函数。
map、filter、sort_by、find这些要接收函数值,第 15 章讲完函数作为值再用。
本章小结
[1, 2, 3]是列表字面量,默认是MutableList[Int];let xs: List[Int] = [...]得到只读列表。- 下标从 0 开始;越界是运行时错误
SPR-RUNTIME-EXCEPTION,不是编译错误。 - 空字面量
[]必须写元素类型,否则SPR-TYPE-INFER。 MutableList可以当List传,是同一份数据的只读视角;toList()做只读快照;toMutableList()是只读列表的复制,对可改列表返回它自己。- 改内容的方法只在
MutableList上;写在List上是SPR-COLLECTION-IMMUTABLE。 ==按内容和顺序比较;sort()就地升序排序。@std/lists.spr提供sorted、reversed、distinct、index_of、sum、take、drop等;需要函数值的函数留到第 15 章。
动手练习
练习 1(热身) 把 [3, 1, 4, 1, 5] 里的每个元素加 10,放进一个新列表并打印。
提示:先 let out: MutableList[Int] = [],用 for n in numbers: 遍历,循环里 out.append(n + 10)。
参考答案
let numbers = [3, 1, 4, 1, 5]
let bigger: MutableList[Int] = []
for n in numbers:
bigger.append(n + 10)
print(bigger)[13, 11, 14, 11, 15]练习 2 写一个函数 largest(xs: List[Int]) -> Int,返回列表里最大的元素。假设列表非空。
提示:先把 xs[0] 当作临时最大值;循环里遇到更大的就替换它。
参考答案
func largest(xs: List[Int]) -> Int:
var best = xs[0]
for x in xs:
if x > best:
best = x
return best
print(largest([4, 9, 2, 7]))9练习 3 给名字列表 ["Ada", "Bob", "Cyd"] 打印带编号的名单:1. Ada、2. Bob、3. Cyd。
提示:for i in range(0, names.size()),编号是 i + 1;数字和字符串可以直接用 + 拼,参考答案显式写了 .toString()。
参考答案
let names = ["Ada", "Bob", "Cyd"]
for i in range(0, names.size()):
print((i + 1).toString() + ". " + names[i])1. Ada
2. Bob
3. Cyd练习 4 用 @std/lists 处理 [3, 1, 3, 2, 1]:打印去重后的列表和倒序列表。
提示:import "@std/lists.spr" as lists,然后用 lists.distinct(raw) 和 lists.reversed(raw)。
参考答案
import "@std/lists.spr" as lists
let raw = [3, 1, 3, 2, 1]
print(lists.distinct(raw))
print(lists.reversed(raw))[3, 1, 2]
[1, 2, 3, 1, 3]下一章把单列的列表扩展成"按键找值"的映射,以及不许重复的集合:映射和集合。
