6. Arrays and maps
Most programs work with collections. Tern has two: arrays ([T], an ordered list of values of one type) and maps ({K: V}, a table from keys to values). This chapter shows how to build, read, change, loop over, and search both, and the one rule about changing a collection while you loop over it.
Arrays
An array literal is a list in square brackets. All elements have the same type, and the array's type is written [int], [str], [Point], and so on:
fn main():
scores = [72, 95, 88]
scores.push(61) # add to the end
print(scores, len(scores))
print(scores[0], scores[len(scores) - 1])
scores[1] = 97 # replace an element
last = scores.pop() # remove and return the last element
print(last, scores)
print(88 in scores, 50 in scores)[72, 95, 88, 61] 4
72 61
61 [72, 97, 88]
true false- Indexes start at 0. There are no negative indexes; the last element is
xs[len(xs) - 1]. - Reading or writing outside the array stops the program with a runtime error such as
index 3 out of bounds (length 3). So doespop()on an empty array. x in xstells you whether the array containsx.- It is
push, notappend, andlen(xs), notxs.length. The compiler's hints remind you.
Empty arrays and repeated values
An empty array needs a type, either written out or taken from its first use:
fn main():
names: [str] = []
names.push("ada")
later = []
later.push(2.5) # now `later` is a [float]
zeros = [0] * 5
board = [["."] * 3] * 2 # 2 rows of 3
board[0][1] = "X"
print(names, later, zeros)
print(board)["ada"] [2.5] [0, 0, 0, 0, 0]
[[".", "X", "."], [".", ".", "."]][value] * n makes an array of n copies of a value. For the 2D board, each row is its own copy, so writing board[0][1] changes only the first row. (In Python, [[0] * 3] * 2 shares one row between both, a classic bug. In Tern, values are never shared.)
If the compiler can't tell what an empty array will hold, it asks:
fn main():
todo = []
print(len(todo))2: error: can't tell what `todo` holds; add a type, e.g. `todo: [int] = []`Slices
xs[a..b] is a new array of the elements from index a up to, not including, b. Leave out either end to go to the start or the end:
fn main():
days = ["mon", "tue", "wed", "thu", "fri"]
print(days[1..3], days[..2], days[3..])
rest = days[1..]
rest[0] = "TUE"
print(days[1], rest[0])["tue", "wed"] ["mon", "tue"] ["thu", "fri"]
tue TUEA slice is a copy: changing rest does not change days.
Looping and changing
You already know for x in xs: and for i, x in xs:. While a loop runs over an array, the array can't be changed, because it is unclear what the loop should see:
fn main():
prices = [10, 20, 30]
for p in prices:
if p > 15:
prices.push(p * 2)
print(prices)5: error: can't modify `prices` while looping over it; loop over indices instead: `for i in 0..len(prices):`
5: hint: or build a new array: `out: [T] = []`, push into `out` in the loop, then `prices = out`The two usual fixes are exactly what the error says. To change elements in place, loop over the indexes. To add or drop elements, build a new array:
fn main():
prices = [10, 20, 30]
for i in 0..len(prices):
prices[i] = prices[i] * 2 # in place
print(prices)
cheap: [int] = []
for p in prices:
if p < 50:
cheap.push(p) # a new array
print(cheap)[20, 40, 60]
[20, 40]Sorting, filtering, and mapping
Arrays have three functions that take another function as an argument. You will learn to write such functions yourself in chapter 10; for now, read fn(x) x * 2 as "a function that, given x, returns x * 2":
fn main():
temps = [21, 14, 30, 18, 25]
print(temps.sort_by(fn(t) t)) # ascending
print(temps.sort_by(fn(t) -t)) # descending
print(temps.filter(fn(t) t >= 20)) # keep some
print(temps.map(fn(t) t * 9 / 5 + 32)) # transform each
print(temps) # unchanged[14, 18, 21, 25, 30]
[30, 25, 21, 18, 14]
[21, 30, 25]
[69, 57, 86, 64, 77]
[21, 14, 30, 18, 25]All three return new arrays and leave the original alone. sort_by sorts by a key that is an int, float, or str, and it is stable (equal keys keep their order). For the plain cases there are shortcuts: temps.sorted() is temps.sort_by(fn(t) t), temps.reversed() is a reversed copy, and sum(temps) adds them up (119 here).
Maps
A map stores values under keys. Keys are int or str, and a map remembers the order in which keys were first inserted:
fn main():
stock = {"apples": 12, "pears": 4}
stock["plums"] = 20 # insert
stock["pears"] += 6 # update
print(stock)
print(stock["apples"], len(stock))
print("kiwis" in stock, stock.get("kiwis", 0))
stock.remove("apples")
print(stock.keys(), stock.values())
for fruit, n in stock:
print(fruit, n){"apples": 12, "pears": 10, "plums": 20}
12 3
false 0
["pears", "plums"] [10, 20]
pears 10
plums 20Reading a key that isn't there with m[k] is a runtime error (key not found). When a key might be missing, check with k in m, or use m.get(k, default), which returns the default instead. For "not in", write not (k in m), with the parentheses.
An empty map needs a type too: counts: {str: int} = {}.
Counting and grouping
Two patterns come up constantly. Counting uses get with a default of 0; grouping creates a list the first time a key is seen:
fn main():
words = "the cat and the dog and the bird".split(" ")
counts: {str: int} = {}
for w in words:
counts[w] = counts.get(w, 0) + 1
print(counts)
by_length: {int: [str]} = {}
for w in words:
n = len(w)
if not (n in by_length):
by_length[n] = []
if not (w in by_length[n]):
by_length[n].push(w)
print(by_length){"the": 3, "cat": 1, "and": 2, "dog": 1, "bird": 1}
{3: ["the", "cat", "and", "dog"], 4: ["bird"]}by_length[n].push(w) changes the array stored in the map in place, just as hero.inventory.push(...) changed an array inside a struct in the last chapter.
A map can't be changed while you loop over it either. To update every value, loop over a copy of its keys: for k in m.keys(): m[k] = 0.
Arrays of structs
Collections of structs are the bread and butter of real programs:
struct Task:
title: str
hours: int
done: bool
fn main():
tasks = [Task("write tour", 8, false), Task("fix bug", 2, true), Task("review", 3, false)]
tasks[0].hours -= 1
left = 0
for t in tasks:
if not t.done:
left += t.hours
print(left, "hours left")
for t in tasks.sort_by(fn(t) t.hours):
print(t.hours, t.title)10 hours left
2 fix bug
3 review
7 write tourtasks[0].hours -= 1 changes the element in the array. Note that t = tasks[0] followed by t.hours -= 1 would change only t, a copy. Chapter 9 is all about this.
Try it
Given a list of (name, department) pairs written as two parallel arrays, names = ["ana", "ben", "cy", "dee", "eli"] and depts = ["eng", "ops", "eng", "sales", "ops"], build a map from department to the list of names in it, then print each department with its head count, sorted by department name.
Solution
fn main():
names = ["ana", "ben", "cy", "dee", "eli"]
depts = ["eng", "ops", "eng", "sales", "ops"]
teams: {str: [str]} = {}
for i, d in depts:
if not (d in teams):
teams[d] = []
teams[d].push(names[i])
for d in teams.keys().sort_by(fn(k) k):
print(d, len(teams[d]), teams[d])eng 2 ["ana", "cy"]
ops 2 ["ben", "eli"]
sales 1 ["dee"]Next: 7. Strings. Reference: §8 Arrays, §11 Maps.