Collections: what every collection shares
On this page
Most programs gather values whose number is known only when they run: the primes below some limit, the words of a text, the orders of the day. A collection holds as many values as it is given, and every kind is made, filled and walked the same way. This page covers what they share: building one with the send operator, walking it with each, and working on all of it at once. As a schoolboy, Gauss is said to have added up 1 to 100 in moments, as 50 pairs that each make 101. Here is his sum, the long way:
mod gauss;
import stdio use *;
// collections gives us List, Dict and the rest
import collections use *;
fn main() {
// The numbers 1 to 100, made by a loop that sends one value per pass
let numbers = new List[i32] <- each i in 1 .. 100 yield i;
// each walks a collection, a value at a time
var total = 0;
each n in numbers {
total += n;
}
print <- "1 + 2 + ... + 100 = ", total, "\n";
// map, filter and sum work on the whole collection at once
let odd = numbers.iter().filter(n => n % 2 == 1).count();
let squares = numbers.iter().map(n => n * n).sum();
print <- odd, " are odd, and the squares of all 100 add up to ", squares, "\n";
}
It prints:
1 + 2 + ... + 100 = 5050 50 are odd, and the squares of all 100 add up to 338350
Try this: Gauss's pairs give 50 × 101. Change the 100 to 1000 and check that the pairing still works: 500 pairs of 1001.
Making a collection with the send operator#
new List[i32] makes an empty list. The type in the square brackets says what the list holds, as the types in Result[i32, &str] did on Functions: there is one List, and the brackets fill in the rest, so a List[i32], a List[bool] and a list of structs of your own are the same List holding different things.
Put the send operator straight after new, and it gives the collection all its contents as it is made. It is the arrow that has sent text to print since the first page, and what follows it is a list of entries, each sent in turn. An entry can be more than a single value:
let small = new List[i32] <- 2, 3, 5, 7; // these four values
let zeros = new List[i32] <- 5 of 0; // one value, five times
let flags = new List[bool](8) <- fill false; // room for 8, then filled
let squares = new List[i32] <- each i in 1 .. 10 yield i * i;
// 1 4 9 16 25 36 49 64 81 100
The last entry is the each of Loops, with yield and a value in place of its block: every pass of the loop sends one value into the new collection, as the numbers 1 to 100 went into Gauss's list. It takes the same if after its range, to skip the passes that fail:
let oddSquares = new List[i32] <- each i in 1 .. 10 if i % 2 == 1 yield i * i; // 1 9 25 49 81
Anything each can walk can fill a collection, and that includes a generator. Here is the Fibonacci generator from Functions, handing its values straight into a list, all of them, or only the even ones:
let fibs = new List[i64] <- each fibonacci(12); // 0 1 1 2 3 5 8 13 21 34 55 89 let evenFibs = new List[i64] <- each f in fibonacci(12) if f % 2 == 0 yield f; // 0 2 8 34
With no variable, each sends every value it is handed. All of these work after a collection that already exists, too: the send operator adds its entries to whatever is on its left, so small <- 11, 13 adds two more primes to a list held in a var variable. A dictionary is built the same way, with pairs for entries, as Dict shows. The send operator's entries has every form in full.
Walking a collection with each#
each walks a collection as it walks a range, from the first value to the last. Each pass, the variable is the next item where it lies, a borrow of it rather than a copy, so a large item costs nothing to visit and the collection is whole afterwards. A borrowed number reads like a number: it can be added, compared and printed as total += n does. Where the value itself is wanted, to keep a copy or to hand it to something that takes a value, a * in front fetches it: let last = *n.
While a loop walks a collection, the collection cannot change: an item the loop is looking at could otherwise be moved out from under it. Changing items in place, and taking them out as you go, have methods of their own, on List.
Working on a whole collection: map, filter and sum#
Many loops over a collection only add its values up, count the ones that pass a test, or change each one. A collection can do that for you. iter() hands out its values one at a time, and steps chained after it work on all of them:
let doubled = squares.iter().map(x => x * 2).sum(); // 770: each doubled, then added up let over20 = squares.iter().filter(x => x > 20).count(); // 6: those over 20 let evens = new List[i32] <- each squares.iter().filter(x => x % 2 == 0); // 4 16 36 64 100
x => x * 2 is a closure, in the short form Functions promised: its parameter, an arrow and its body, with no types written, since the list already says what its values are. map turns each value into another, filter keeps the values its test is true of, and sum and count walk what is left and give the answer. Nothing is done until one of those walks it, and then the whole chain runs as one loop. Each step is an adapter: it takes the values coming to it and hands on changed ones, or fewer. take, min, max, any, find and the rest are in the full list.
One thing to know: iter() hands out borrows, like each, and sum wants numbers, so numbers.iter().sum() is refused with the advice to map the borrows to values first: numbers.iter().map(n => *n).sum(). A map that computes a new value, as n * n does, has done that already.
Sharing a collection: Arc#
A collection owns its values, so, like a String, it moves. Handing one to a function gives it away:
fn total(xs List[i32]) i32 { var sum = 0; each x in xs { sum += x; } sum; }
let primes = new List[i32] <- 2, 3, 5, 7, 11;
print <- total(primes), "\n";
print <- primes.len(), "\n"; // Error: This variable's value has been moved out.
When a collection is to be used in several places at once, put it behind an Arc. An Arc is a shared reference: no one variable owns the list. Copying the Arc copies only the reference, never the list, and every copy reaches the same list, which is freed once the last copy is gone:
mod share;
import stdio use *;
import collections use *;
// sync gives us Arc, a reference that may be shared
import sync use Arc;
// total is handed a shared reference to the list, not the list itself
fn total(xs Arc[imm, List[i32]]) i32 {
var sum = 0;
each x in xs {
sum += x;
}
sum;
}
fn main() {
let list = new List[i32] <- 2, 3, 5, 7, 11;
let primes = new Arc[imm, List[i32]](list); // the list moves into the Arc
let also = primes; // a second reference to the same list
print <- total(primes), " ", total(also), " ", primes.len(), "\n"; // 28 28 5
}
The imm in Arc[imm, List[i32]] says the list can be read through the reference and never changed. With nobody able to change it, any number of hands may read it at once, even hands working at the same time, which is just how Actors uses one. References come back in depth in Memory, along with lighter ways to lend a collection for a moment.
The collections, and where to find them#
Two collections carry most programs, and each has a page of its own next:
- List: values in a row, found by their position, growing at the end.
- Dict: values found by a key, such as a word or a name.
The collections package has more of the same family, each made, sent to and walked the same way, and described in the collections reference:
- Set says only whether it holds something: a dictionary of keys alone, for "have I seen this before?"
- Deque is a list that is quick at both ends, for a queue where values join at the back and leave from the front.
- OrderedDict is a dictionary that visits its keys in the order they went in, for output that must come out the same way every time.
- String is a collection too: a row of bytes, read as text.
- Array holds a fixed number of values, set when it is made, such as the three coordinates of a point in space.
You can now build a collection in a line, walk it, and sum it up, filter it or change every value at once. Next, the List up close, sieving out the primes the way Eratosthenes did.