Tern

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)
Output
[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 does pop() on an empty array.
  • x in xs tells you whether the array contains x.
  • It is push, not append, and len(xs), not xs.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)
Output
["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:

Does not compile
fn main():
    todo = []
    print(len(todo))
Compiler output
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])
Output
["tue", "wed"] ["mon", "tue"] ["thu", "fri"]
tue TUE

A 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:

Does not compile
fn main():
    prices = [10, 20, 30]
    for p in prices:
        if p > 15:
            prices.push(p * 2)
    print(prices)
Compiler output
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)
Output
[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
Output
[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)
Output
{"apples": 12, "pears": 10, "plums": 20}
12 3
false 0
["pears", "plums"] [10, 20]
pears 10
plums 20

Reading 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)
Output
{"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)
Output
10 hours left
2 fix bug
3 review
7 write tour

tasks[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])
Output
eng 2 ["ana", "cy"]
ops 2 ["ben", "eli"]
sales 1 ["dee"]

Next: 7. Strings. Reference: §8 Arrays, §11 Maps.

Source: docs/tour/06-arrays-and-maps.md. Every example on this page is compiled and run by tern x test docs.