List: values in a row that grows
On this page
A List keeps values in a row, in the order they arrive, finds each by its position, and grows at the end as values are sent to it. It is the collection most programs reach for first. This page shows how to make one, read and change its values by position, change them all at once, take them out, and sort them. Eratosthenes found the primes by crossing out the multiples of each one he found; this sieve also counts how many different primes divide every number on the way:
mod sieve;
import stdio use *;
// collections gives us List, Dict and the rest
import collections use *;
fn main() {
// Positions in a list are counted with usize, so the limit is one
let limit = 1000usize;
// For every number below the limit, how many primes divide it:
// room for 1000 values, every one filled with 0 to begin with
var factors = new List[i32](limit) <- fill 0;
// A list that starts empty, and grows as primes are sent to it
var primes = new List[usize];
// A number that no smaller prime divides is prime,
// and it marks every multiple of itself
each n in 2usize ..< limit {
continue if factors[n] > 0;
primes <- n;
each m in n ..< limit by n {
factors[m] += 1;
}
}
print <- primes.len(), " primes below ", limit, ", the last ", primes[primes.len() - 1], "\n";
print <- "210 has ", factors[210], " different prime factors\n";
}
It prints:
168 primes below 1000, the last 997 210 has 4 different prime factors
Try this: 210 is 2 × 3 × 5 × 7. The first number with five different prime factors is 2310, past the end of this list. Raise the limit to 3000 and ask factors about it.
Making a list and sending values to it#
new List[usize] makes an empty list of usize values, and new List[i32](limit) <- fill 0 makes one with room for limit values, then fills that room with zeros. Whatever a list holds, the compiler holds it to: primes <- true is refused, with "A bool is not a number, and usize is wanted here."
The send operator puts a value on the end of a list, primes <- n, and takes several, separated by commas: primes <- 1009, 1013. The list makes room as it needs it. The method it calls is push, which may also be called by name: primes.push(n). len() says how many values a list holds. All the ways of building a list in one go, from Collections, work here: new List[i32] <- 2, 3, 5, 7, 5 of 0, each … yield.
Finding a value by its position#
A value is found by its position, counted from 0: primes[0] is 2. A position is a usize, the unsigned type for counting things in memory, which is why the sieve counts with one. In a list held in a var variable, a value can be changed where it stands, factors[m] += 1, or replaced, factors[m] = 0, and swap(i, j) trades two. A position past the end stops the program with a panic that says what went wrong: "index 5 is out of range for a length of 2".
Like the variable of an each, primes[0] is the value where it lies in the list, a borrow, not a copy. It reads like the value in arithmetic, a comparison or a print, as the sieve's factors[n] > 0 does. Where the value itself is wanted, a * fetches a copy: let first = *primes[0], or if *flags[1] for a list of bool, since a condition must be a bool itself.
That borrow has a consequence worth knowing early. A list keeps its values in one block of memory, and growing may move them all to a bigger one. So while a borrow of a value is still to be used, the list may be read but not grown, and the compiler refuses the push that would leave the borrow pointing at nothing:
var list = new List[i32] <- 10, 20; let first = list[0]; // a borrow of the first value list.push(30); // refused print <- first, "\n";
The compiler names both places: "Error 1168: 'list' is borrowed (by '[]' at …), and that borrow is used again at …. It may not be borrowed mutably until after that last use."
Copying the value out first, let first = *list[0], leaves nothing to wait for, and so does moving the push after the borrow's last use. Borrowed references has the rule in full.
Changing every value, and taking them out#
A plain each only reads. To change every value where it stands, walk mutItems(), which lends each one for changing, and write through it with *. indexed() hands out each value's position beside it:
var xs = new List[i32] <- 3, 1, 2;
each x in xs.mutItems() {
*x *= 10; // xs is now 30 10 20
}
each i, x in xs.indexed() {
print <- i, ":", x, " "; // 0:30 1:10 2:20
}
A list of values that move rather than copy, such as Strings, gives them up one at a time with drain(): each value is moved out of the list into the loop's variable, and the list is left empty, ready to be filled again. clear() empties a list without looking at its values.
var names = new List[String] <- String.from("Euclid"), String.from("Hypatia");
var kept = List[String].empty();
each name in names.drain() {
kept <- name; // the String itself moves on: names is now empty
}
Sorting#
sortBy sorts a list in place. Its closure is handed two values and says which comes first: a negative number for the first, a positive one for the second. Smallest first is xs.sortBy((a, b) => a - b), and largest first, for a table of scores, scores.sortBy((a, b) => b - a).
When there may be nothing to give#
Some questions a list can be asked have no answer. pop() takes the last value off, but a list may be empty; get(i) asks for a position without risking a panic, but the position may be past the end. Both give back an Option, which holds the value if there is one, and which the next page explains at its first lookup. Every List method, the ones for handing a list's values to C among them, is in the collections reference.
For a fixed number of values there is also Array; see the reference.
You can now keep values in a row, find and change them by position, change them all, take them out and sort them. Next, the other way of finding a value: by a key, such as a word, with Dict.