Chapter 5: Collections

What you'll learn: the four built-in collection types (list, dict, set, tuple), indexing and slicing, the methods each collection has, list comprehensions, spread, membership tests, and what happens when you copy a collection or pass it to a function.

Scripts spend most of their time on collections: lines of a log, rows of a CSV file, a dictionary of settings, a set of IDs already seen. This chapter covers the built-in collections and the mistakes people make with them in their first week.

The Four Collection Types

Choose by how you will use the data: by position, a list; by key, a dict; "have I seen this?", a set; a small fixed group such as a pair, a tuple.

Lists

A list literal is a comma-separated sequence in square brackets. The element type is inferred from the elements; annotate it when there is nothing to infer from:

@mode(host.scripted)

let numbers = [1, 2, 3, 4, 5];
let names: list[string] = ["Alice", "Bob", "Charlie"];
let pending: list[int] = [];

println(numbers);
println(names.length());
println(pending.is_empty());

Listing 5-1: List literals

[1, 2, 3, 4, 5]
3
true

Indexing

Indexes start at 0. A negative index counts from the end, so -1 is the last element:

let items = [10, 20, 30, 40, 50];
#            0   1   2   3   4
#           -5  -4  -3  -2  -1

println(items[0]);
println(items[-1]);
println(items.length());

10
50
5

Mistake: an index past the end

An index outside the list is not a compile error — the compiler does not know how long the list will be — but it throws IndexError at run time:

let scores = [88, 72, 95];
println(scores[3]);

Uncaught IndexError: list index 3 out of range (len 3)
  at <main> (main.lpscr:3:9)

scores has three elements, at indexes 0, 1 and 2. When an index comes from outside the program — a command-line argument, a line number in a file — check it against length() first:

let scores = [88, 72, 95];
let wanted = 3;

if (wanted < scores.length()) {
    println(scores[wanted]);
} else {
    println(i"there is no score #{$ wanted $}");
}

there is no score #3

The same IndexError comes from first(), last() and pop() on an empty list. Chapter 10 shows how to catch it when a check is not practical.

Slicing

A slice xs[start:end:step] returns a new list. Every part is optional; start defaults to 0, end to the length and step to 1. Out-of-range bounds are clamped rather than reported (§1-5.3):

let items = [10, 20, 30, 40, 50];

println(items[1:4]);     # elements 1, 2 and 3
println(items[2:]);      # from 2 to the end
println(items[:3]);      # the first three
println(items[-2:]);     # the last two
println(items[::-1]);    # reversed
println(items[0:5:2]);   # every second element
println(items[1:100]);   # the end is clamped to the length

Listing 5-2: Slices

[20, 30, 40]
[30, 40, 50]
[10, 20, 30]
[40, 50]
[50, 40, 30, 20, 10]
[10, 30, 50]
[20, 30, 40, 50]

xs.slice(a, b) is the method spelling of xs[a:b], and xs.slice(a) of xs[a:].

Changing a List

var items = [1, 2, 3];

items.push(4);               # append at the end; `append` is the same method
items[0] = 99;               # replace one element
println(items);

items[1:3] = [20, 30, 40];   # replace a slice; the length may change
println(items);

let last = items.pop();      # remove and return the last element
let first = items.remove(0); # remove and return the element at an index
println(i"{$ first $} and {$ last $} removed, {$ items $} left");

items = items + [5, 6];      # `+` builds a new list
println(items);

Listing 5-3: Adding, replacing and removing elements

[99, 2, 3, 4]
[99, 20, 30, 40, 4]
99 and 4 removed, [20, 30, 40] left
[20, 30, 40, 5, 6]

Slice assignment needs a var binding: it rebinds the variable to the new list.

Common List Methods

The Language Reference lists every list method (§1-4.1.5); these are the ones you will use most. Several have two spellings, such as length() and len(), or indexOf and index_of; both are part of the language.

var nums = [3, 1, 4, 1, 5, 9, 2, 6];

println(nums.length());
println(nums.contains(4));
println(nums.indexOf(1));          # first occurrence
println(nums.indexOf(7));          # -1 when absent
println(nums.first());
println(nums.last());
println(nums.join(", "));

nums.sort(func(a: int, b: int) => a - b);
println(nums);
nums.reverse();
println(nums);

Listing 5-4: Searching, joining, sorting and reversing

8
true
1
-1
3
6
3, 1, 4, 1, 5, 9, 2, 6
[1, 1, 2, 3, 4, 5, 6, 9]
[9, 6, 5, 4, 3, 2, 1, 1]

sort and reverse change the list in place and return nothing. To keep the original, sort a copy: var sorted = nums.clone();.

Mistake: sort() with no comparator

Python's sort() and JavaScript's sort() need no argument. Loup's does:

@mode(host.scripted)

var scores = [88, 72, 95, 60];
scores.sort();
println(scores);

main.lpscr:4:1: error[E0001]: function 'sort' expects 1 argument(s), but 0 provided

The comparator is a function that takes two elements and returns a negative number when the first should come first, zero when they are equal, and a positive number otherwise. Loup has no overloading, so there is no separate zero-argument form. Pass the comparator; to sort descending, swap the operands:

@mode(host.scripted)

var scores = [88, 72, 95, 60];
scores.sort(func(a: int, b: int) => b - a);
println(scores);

var names = ["mallory", "alice", "bob"];
names.sort(func(a: string, b: string) => a.compareTo(b));
println(names);

[95, 88, 72, 60]
["alice", "bob", "mallory"]

Other methods that do not exist on lists, and what to use instead: sorted() (clone, then sort), forEach (a for loop), distinct() (a set, below), take(n) and drop(n) (slices xs[:n] and xs[n:]).

map, filter and reduce

The higher-order methods take a function. The short lambda form is func(params) => expression (Chapter 3):

let nums = [3, 1, 4, 1, 5, 9, 2, 6];

println(nums.map(func(n: int) => n * 2));
println(nums.filter(func(n: int) => n > 3));
println(nums.reduce(0, func(total: int, n: int) => total + n));
println(nums.any(func(n: int) => n > 8));
println(nums.all(func(n: int) => n > 0));

Listing 5-5: Transforming, filtering and folding a list

[6, 2, 8, 2, 10, 18, 4, 12]
[4, 5, 9, 6]
31
true
true

reduce (also spelled fold) takes the starting value first and the combining function second.

Mistake: leaving out the lambda's parameter type

In TypeScript or Python you would write x => x * 2. In Loup a lambda parameter without a type annotation is Any, and Any has no *:

@mode(host.scripted)

let prices = [12, 7, 30];
let doubled = prices.map(func(p) => p * 2);
println(doubled);

main.lpscr:4:26: error[E0001]: argument 1 of 'map': expected 'fn(int): <error>', found 'fn(Any): <error>'
main.lpscr:4:37: error[E_OPERATOR_MISSING]: type 'Any' does not implement 'Mul' required for operator '*' (E_OPERATOR_MISSING)

The first message says map wanted a function taking int and got one taking Any; the second is the same problem seen from inside the lambda. Write the type:

@mode(host.scripted)

let prices = [12, 7, 30];
let doubled = prices.map(func(p: int) => p * 2);
println(doubled);

[24, 14, 60]

List Comprehensions

Chapter 4 introduced the comprehension, [expression for name in source if condition], over a range. The source can be any collection, a dict's entries() destructured into names, or several for clauses in a row. As in Chapter 4, the clauses take no parentheses:

let words = ["loup", "is", "a", "small", "language"];
let lengths = [w.length() for w in words];
let longWords = [w.toUpperCase() for w in words if w.length() > 3];

let ages = {"ana": 34, "ben": 17, "chloe": 52};
let adults = [name for (name, age) in ages.entries() if age >= 18];

let matrix = [[1, 2], [3, 4], [5, 6]];
let flat = [cell for row in matrix for cell in row];

println(lengths);
println(longWords);
println(adults);
println(flat);

Listing 5-6: List comprehensions over lists and dicts

[4, 2, 1, 5, 8]
["LOUP", "SMALL", "LANGUAGE"]
["ana", "chloe"]
[1, 2, 3, 4, 5, 6]

With several for clauses, the leftmost is the outer loop: flat takes each row, then each cell in it. A comprehension is usually clearer than the same map and filter chain; use whichever reads better.

⚠ Planned. The Language Reference (§1-5.2) also defines dict comprehensions ({k: v for (k, v) in d.entries()}) and set comprehensions ({w.length() for w in words}). Loup 1.25 does not parse them; build the dict or set with a for loop.

Dicts

A dict maps keys to values and remembers the order in which keys were inserted:

@mode(host.scripted)

var ages = {"alice": 30, "bob": 25};

println(ages["alice"]);               # throws KeyError if the key is missing
println(ages.get("carol") ?? 0);      # `get` returns an Option
println("alice" in ages);             # key membership
println(ages.contains("bob"));

ages["carol"] = 41;                   # insert or replace
let removed = ages.remove("bob");     # also an Option
println(ages);

for ((name, age) in ages.entries()) {
    println(i"{$ name $} is {$ age $}");
}
for (name in ages.keys()) {
    println(name);
}

Listing 5-7: Reading, writing and iterating a dict

30
0
true
true
{"alice": 30, "carol": 41}
alice is 30
carol is 41
alice
carol

d[key] and d.get(key) are deliberately different: the subscript throws KeyError when the key is absent, and get returns Option[V] — Some(value) or None. The ?? operator unwraps an Option or supplies a default. keys(), values() and entries() return lists in insertion order, and for (k in d) iterates the keys.

Keys must be hashable. Strings, numbers, char, bool, and tuples of them work as keys. The Language Reference also allows structs and enums whose fields are hashable, but in Loup 1.25 a lookup with an equal struct or enum value does not find the entry (it throws KeyError), so use one of the other key types for now — for example a tuple (x, y) instead of a Point struct.

Mistake: reading a key that is not there

let ports = {"http": 80, "https": 443};
println(ports["ssh"]);

Uncaught KeyError: key 'ssh' not found in dict
  at <main> (main.lpscr:3:9)

When a key may be missing, use get and decide what absence means:

let ports = {"http": 80, "https": 443};
let ssh = ports.get("ssh") ?? 22;
println(ssh);

if ("ftp" in ports) {
    println(ports["ftp"]);
} else {
    println("no ftp port configured");
}

22
no ftp port configured

Mistake: values of different types

A dict literal's values must share one type. A configuration mixing strings, numbers and booleans is rejected:

@mode(host.scripted)

let config = {"host": "localhost", "port": 8080, "debug": true};
println(config);

main.lpscr:3:14: error[E0001]: dict literal has incompatible value types: first value is 'string', but found different types

The compiler inferred string from the first value and then found an int. If you really want a heterogeneous dict — for example to mirror a JSON object — say so with the type dict[string, Any]:

@mode(host.scripted)

let config: dict[string, Any] = {"host": "localhost", "port": 8080, "debug": true};
println(config);

{"host": "localhost", "port": 8080, "debug": true}

Values read from a dict[string, Any] are Any, and you must check or convert them before use. For configuration with a fixed shape, a struct (Chapter 6) is usually better.

Sets

A set holds each value at most once:

@mode(host.scripted)

let primes = {2, 3, 5, 7, 11};
println(5 in primes);

var seen: set[string] = {};          # annotated: a bare {} is an empty dict
for (word in ["to", "be", "or", "not", "to", "be"]) {
    seen.add(word);
}
println(seen);
println(seen.length());

seen.remove("or");
println(seen.contains("or"));

Listing 5-8: Building a set of unique words

true
{"to", "be", "or", "not"}
4
false

An empty {} is a dict unless the binding's type says otherwise; set[string]() also makes an empty set.

The built-in set has add, remove, contains (and in), and length()/len(). It has no union, intersection or difference methods in Loup 1.25, so write the ones you need:

func intersection(a: set[string], b: set[string]): set[string] {
    var both: set[string] = {};
    for (x in a) {
        if (x in b) {
            both.add(x);
        }
    }
    return both;
}

let monday = {"ana", "ben", "chloe"};
let tuesday = {"ben", "chloe", "dev"};
println(intersection(monday, tuesday));

{"ben", "chloe"}

Tuples

A tuple groups a fixed number of values, possibly of different types. Its type is written (int, string) or tuple[int, string]:

@mode(host.scripted)

let pair = (42, "hello");
let single = (42,);                  # a one-element tuple needs the comma
println(pair.0);
println(pair.1);

let (num, msg) = pair;               # destructuring
println(i"{$ num $} / {$ msg $}");

let points = [(1, 2), (3, 4)];
for ((x, y) in points) {
    println(i"({$ x $}, {$ y $})");
}

println((1, "a") == (1, "a"));       # tuples compare element by element

Listing 5-9: Tuple fields, destructuring and equality

42
hello
42 / hello
(1, 2)
(3, 4)
true

The most common use is returning more than one value from a function:

func minMax(items: list[int]): (int, int) {
    var lo = items[0];
    var hi = items[0];
    for (n in items) {
        if (n < lo) { lo = n; }
        if (n > hi) { hi = n; }
    }
    return (lo, hi);
}

let (lowest, highest) = minMax([3, 1, 4, 1, 5, 9]);
println(i"range {$ lowest $}..{$ highest $}");

range 1..9

A tuple is not a collection you loop over: for (field in someTuple) is a compile error. When the fields deserve names, or the same shape appears in several places, use a struct (Chapter 6).

Spread

Inside a list literal, *xs inserts the elements of xs; inside a dict literal, **d inserts the entries of d, with later entries replacing earlier ones:

let middle = [1, 2, 3];
println([0, *middle, 4]);

let defaults = {"host": "localhost", "port": "8080", "tls": "off"};
let production = {**defaults, "host": "prod.example.com", "tls": "on"};
println(production);
println(defaults);

[0, 1, 2, 3, 4]
{"host": "prod.example.com", "port": "8080", "tls": "on"}
{"host": "localhost", "port": "8080", "tls": "off"}

Spreading builds a new collection; defaults is unchanged.

⚠ Planned. Set spread ({*s1, *s2}, §1-5.8) does not parse in Loup 1.25.

Membership

in and not in test membership: an element of a list or set, a key of a dict, or a substring of a string:

println(3 in [1, 2, 3]);
println("name" in {"name": "Al"});
println(5 in {1, 3, 5, 7});
println("ou" in "loup");
println(4 not in [1, 2, 3]);

true
true
true
true
true

A list is searched element by element; dicts and sets use hashing. For repeated membership tests on a large collection, build a set once.

Collections Are Values

Assigning a collection to another binding copies it (§1-10.3, ruling COLL-1). Changing the copy does not change the original:

@mode(host.scripted)

var original = [1, 2];
var copy = original;
copy.push(3);

println(original);
println(copy);

Listing 5-10: Binding a list copies it

[1, 2]
[1, 2, 3]

The implementation shares storage until one side writes, so the copy is cheap until you change it.

let and var are about the binding: a let binding cannot be reassigned (xs = [3] is cannot assign to immutable binding 'xs'). In Loup 1.25, let does not stop element writes or calls such as push on the list it holds; use var whenever you intend to change a collection, so the intent is visible.

Mistake: changing a list parameter

A function parameter without a verb is a read-only borrow of the caller's value (Chapter 19). Calling a mutating method on it is an error:

@mode(host.scripted)

func addDefault(tags: list[string]): void {
    tags.push("untagged");
}

var tags: list[string] = [];
addDefault(tags);
println(tags);

main.lpscr:4:5: error[E_READS_MUTATION]: E_READS_MUTATION: parameter 'tags' is a `reads` borrow (a parameter without a verb is read-only, §3-2.4.9) and cannot be mutated (`push` called on it); declare it `edits` and pass `edits: …` to change the caller's value, or copy it into a local first

The message offers two fixes. If the function should change the caller's list, declare the parameter edits and acknowledge it at the call site with edits::

@mode(host.scripted)

func addDefault(edits tags: list[string]): void {
    tags.push("untagged");
}

var tags: list[string] = [];
addDefault(edits: tags);
println(tags);

["untagged"]

Leaving out edits: at the call is E_VERB_REQUIRED: the call site must show that the call can change tags. If the function only needs a modified version for itself, copy the parameter into a local var and return the result instead.

Mutating a collection while looping over it

The Language Reference makes it an error to change a collection inside a for loop over that same collection (E_BORROW_LOOP_MUTATION, §1-6.4; a run-time warning in scripts). Loup 1.25 does not check this yet, and the loop sees the change:

@mode(host.scripted)

var queue = [1, 2, 3];
for (n in queue) {
    if (n == 2) {
        queue.push(99);
    }
    println(n);
}

1
2
3
99

The loop processed the element it added. In a less contrived loop — one that pushes on every pass — it never ends. Collect the changes and apply them after the loop:

@mode(host.scripted)

var queue = [1, 2, 3];
var additions: list[int] = [];
for (n in queue) {
    if (n == 2) {
        additions.push(99);
    }
    println(n);
}
queue = queue + additions;
println(queue);

1
2
3
[1, 2, 3, 99]

Comparing collections

Known gap. In Loup 1.25, == on two lists, dicts or sets compares identity, not contents: [1, 2] == [1, 2] is false, and so is a == b after let b = a; (because b is a copy). Ruling EQ-3 makes collection equality element-wise, but the toolchain does not implement it yet. Compare contents yourself until it does.

let expected = [1, 2, 3];
let actual = [1, 2, 3];
println(expected == actual);

false

A small helper does the element-wise comparison:

func sameInts(a: list[int], b: list[int]): bool {
    if (a.length() != b.length()) {
        return false;
    }
    for (i in 0..a.length()) {
        if (a[i] != b[i]) {
            return false;
        }
    }
    return true;
}

println(sameInts([1, 2, 3], [1, 2, 3]));
println(sameInts([1, 2, 3], [1, 2]));

true
false

Tuples, structs and enums already compare by value.

Practical Example: Word Frequencies

@mode(host.scripted)

## Count how often each word occurs, ignoring case.
func wordFrequencies(text: string): dict[string, int] {
    var freq: dict[string, int] = {};
    for (word in text.toLowerCase().split(" ")) {
        let cleaned = word.trim();
        if (cleaned.length() == 0) {
            continue;
        }
        freq[cleaned] = (freq.get(cleaned) ?? 0) + 1;
    }
    return freq;
}

## The `n` most frequent words, most frequent first.
func topWords(freq: dict[string, int], n: int): list[(string, int)] {
    var ranked = freq.entries();
    ranked.sort(func(a: (string, int), b: (string, int)) => b.1 - a.1);
    return ranked[:n];
}

let text = "The quick brown fox jumps over the lazy dog the fox";
let freq = wordFrequencies(text);

println("Top 3:");
for ((word, count) in topWords(freq, 3)) {
    println(i"  {$ word $} x {$ count $}");
}

Listing 5-11: Counting words with a dict, a sort and tuple destructuring

Top 3:
  the x 3
  fox x 2
  quick x 1

entries() turns the dict into a list of (word, count) tuples, the comparator sorts by count, and the slice keeps the first n.

Summary

• list[T] is ordered and indexed from 0 (negative indexes count from the end); dict[K, V] maps keys to values in insertion order; set[T] holds unique values; tuples group a fixed number of values.
• An index out of range throws IndexError; a missing key with d[k] throws KeyError; d.get(k) returns an Option you can default with ??.
• sort requires a comparator; lambda parameters need types.
• List comprehensions are written [expr for x in xs if cond]; dict and set comprehensions, set algebra methods and set spread are not in Loup 1.25.
• Collections are values: binding one to another name copies it. A parameter is read-only unless declared edits and passed with edits:.
• Two known gaps: changing a collection inside a for over it is not checked, and == on collections compares identity.

Try It Yourself

1. Extend Listing 5-11 to read its text from a file named on the command line (readText(args()[0])) and print the top five words.
2. Write unique(words: list[string]): list[string] that keeps the first occurrence of each word, using a set to remember what you have seen.
3. Write union(a: set[int], b: set[int]): set[int] and difference(a: set[int], b: set[int]): set[int] in the style of the intersection function above.
4. Write a function that takes edits xs: list[int] and removes every negative number, and call it on a var list.