Chapter 6: Collections

What you'll learn. The built-in collections list[T], dict[K, V] and set[T], plus tuples: their literals, the methods each one has, slicing, list comprehensions, and what happens when you assign a collection or pass it to a function.

Why it matters. A web app is mostly collections: the items in a cart, form errors keyed by field name, the set of selected rows, a pair of values returned from one function. Loup's collections behave differently from JavaScript arrays and Python lists in one important way — assignment copies them — and the method set is deliberately small.

All collections are generic: the element type goes in square brackets (list[string], dict[string, int]). The type of a literal is inferred from its elements; an empty literal needs an annotation.

list[T]

A list is an ordered, growable sequence. Indexes start at 0, and a negative index counts from the end.

@mode(web.compiled)

func main(): void {
    var cart: list[string] = ["milk", "eggs"];
    cart.push("bread");
    cart.append("butter");
    println(cart);
    println(cart.length());

    println(cart[0]);
    println(cart[-1]);
    cart[1] = "free-range eggs";

    println(cart.contains("bread"));
    println(cart.index_of("bread"));
    println(cart.index_of("jam"));

    let last = cart.pop();
    let first = cart.remove(0);
    println(i"removed {$ first $} and {$ last $}");
    println(cart.join(", "));

    let empty: list[int] = [];
    println(empty.is_empty());
}

Listing 6-1: Everyday list operations

["milk", "eggs", "bread", "butter"]
4
milk
butter
true
2
-1
removed milk and butter
free-range eggs, bread
true

The full list method set, from the Language Reference (§1-4.1.5), is: length()/len(), is_empty(), push/append, pop(), get(i), set(i, v), remove(i), first(), last(), clear(), contains, index_of, slice, reverse(), sort(comparator), join(sep), clone(), iter(), map, filter, reduce/fold, any, all and to_string(). Any other name is a type error. index_of returns -1 when the element is missing.

Length is a method, and there is no global len function. Both are common habits:

@mode(web.compiled)

func main(): void {
    let cart = ["milk", "eggs"];
    println(len(cart));
}

main.lpweb:5:13: error[E0001]: undefined identifier `len`

@mode(web.compiled)

func main(): void {
    let cart = ["milk", "eggs"];
    println(cart.length);
}

main.lpweb:5:13: error[E0001]: type 'list[string]' does not support member access

The second message means that length is not a field. Call it: cart.length().

Out-of-range indexes

Indexing is bounds-checked. An index past either end raises IndexError when the program runs; you never get a garbage value or a silent None:

@mode(web.compiled)

func main(): void {
    let slots = [10, 20, 30];
    println(slots[3]);
}

Uncaught IndexError: list index 3 out of range (len 3)
  at main (main.lpweb:5:13)

get(i) behaves the same way, and so do pop(), first() and last() on an empty list. Check the length first, or catch the error:

@mode(web.compiled)

func slotOrDefault(slots: list[int], i: int, fallback: int): int {
    if (i >= 0 and i < slots.length()) {
        return slots[i];
    }
    return fallback;
}

func main(): void {
    let slots = [10, 20, 30];
    println(slotOrDefault(slots, 1, 0));
    println(slotOrDefault(slots, 3, 0));
}

Listing 6-2: Guarding an index

20
0

Slicing

A slice xs[start:end] is a new list holding the elements from start up to, but not including, end. Either bound may be left out, a negative bound counts from the end, and out-of-range bounds are clamped. xs.slice(start, end) is the same operation as a method.

@mode(web.compiled)

func main(): void {
    let nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
    println(nums[0:3]);
    println(nums[7:]);
    println(nums[:2]);
    println(nums[-3:]);
    println(nums.slice(3, 7));
    println(nums[8:50]);
}

Listing 6-3: Slices

[0, 1, 2]
[7, 8, 9]
[0, 1]
[7, 8, 9]
[3, 4, 5, 6]
[8, 9]

The separator is a colon. The range form 0..3 from Chapter 5 is only allowed as a loop source, so it is not a slice:

@mode(web.compiled)

func main(): void {
    let nums = [0, 1, 2, 3, 4, 5];
    println(nums[0..3]);
}

main.lpweb:5:18: error[E0001]: E_RANGE_FORM_MISPLACED: the range form `start..end` is permitted only as the iteration source of a `for` loop or a comprehension clause (§1-6.4)

List comprehensions

A comprehension builds a list from one or more for clauses and optional if filters. Unlike a for statement, its clauses are written without parentheses (Language Reference §1-5.2):

@mode(web.compiled)

func main(): void {
    let nums = [1, 2, 3, 4, 5, 6];
    let evenSquares = [n * n for n in nums if n % 2 == 0];
    println(evenSquares);

    let squares = [n * n for n in 1..6];
    println(squares);

    let pairs = [(r, c) for r in 0..2 for c in 0..3 if r != c];
    println(pairs);
}

Listing 6-4: List comprehensions

[4, 16, 36]
[1, 4, 9, 16, 25]
[(0, 1), (0, 2), (1, 0), (1, 2)]

Carrying the parentheses over from the for statement breaks the parse:

@mode(web.compiled)

func main(): void {
    let nums = [1, 2, 3, 4];
    let evens = [n for (n in nums) if (n % 2 == 0)];
    println(evens);
}

main.lpweb:5:27: error[E0001]: expected RParen, found In
main.lpweb:5:34: error[E0001]: expected RBracket, found RParen
main.lpweb:5:34: error[E0003]: expected `;`
main.lpweb:5:51: error[E0002]: expected `{`
main.lpweb:5:51: error[E0001]: expected expression

The first message is the useful one: inside the brackets, (n in nums) reads as a parenthesized expression, and the parser expected it to close before in.

⚠ Planned. The Language Reference also specifies set comprehensions ({w.length() for w in words}) and dict comprehensions ({w: w.length() for w in words}). Loup 1.25.1 does not parse them; build the set or dict with a for loop.

map, filter, reduce and friends

The higher-order methods take a function and return a new value; the original list is unchanged. fold is another name for reduce.

@mode(web.compiled)

func main(): void {
    let prices = [120, 45, 300, 80];

    let withTax = prices.map(func(p: int) => p * 108 // 100);
    let large = prices.filter(func(p: int) => p >= 100);
    let total = prices.reduce(0, func(sum: int, p: int) => sum + p);
    let discounted = prices.filter(func(p: int) => p >= 100).map(func(p: int) => p * 9 // 10);

    println(withTax);
    println(large);
    println(total);
    println(discounted);
    println(prices.any(func(p: int) => p > 250));
    println(prices.all(func(p: int) => p > 50));
}

Listing 6-5: Higher-order list methods

[129, 48, 324, 86]
[120, 300]
545
[108, 270]
true
false

Lambda parameters need their types. Without them the parameter is Any, and the checker can neither match the function to map nor apply * to it:

@mode(web.compiled)

func main(): void {
    let prices = [120, 45, 300];
    let withTax = prices.map(func(p) => p * 108 // 100);
    println(withTax);
}

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

Write func(p: int) => …, as in Listing 6-5.

Sorting

sort and reverse change the list in place, so the list must be a var. sort takes a required comparator that returns a negative number, zero or a positive number. There is no zero-argument natural-order sort:

@mode(web.compiled)

func main(): void {
    var names = ["Cy", "Ana", "Ben"];
    names.sort();
    println(names);
}

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

Pass the comparison you want:

@mode(web.compiled)

func main(): void {
    var names = ["Cy", "Ana", "Ben"];
    names.sort(func(a: string, b: string) => a.compareTo(b));
    println(names);

    var scores = [("Ana", 91), ("Ben", 78), ("Cy", 85)];
    scores.sort(func(a: (string, int), b: (string, int)) => b.1 - a.1);
    println(scores);

    scores.reverse();
    println(scores);
}

Listing 6-6: Sorting with a comparator

["Ana", "Ben", "Cy"]
[("Ana", 91), ("Cy", 85), ("Ben", 78)]
[("Ben", 78), ("Cy", 85), ("Ana", 91)]

More list helpers come from the standard library

Lists have no zip, find, groupBy or sum methods. Those are functions in the system.collections module. A web.compiled file cannot import a standard-library module in 1.25.1, because the modules are compiled as host.scripted and a web.compiled module may import only other web.compiled modules (see Chapter 2, The standard library from web code):

@mode(web.compiled)

from system.collections import (zip);

func main(): void {
    let names = ["Ana", "Ben", "Cy"];
    let scores = [91, 78, 85];
    for ((name, score) in zip(names, scores)) {
        println(i"{$ name $}: {$ score $}");
    }
}

main.lpweb:3:1: error[E0001]: `@mode(web.compiled)` module cannot import `@mode(host.scripted)` module
  note: `@mode(web.compiled)` modules can only import other `@mode(web.compiled)` modules
  note: error code: E_COMPILED_IMPORT_SCRIPTED

In a web.scripted file the import works. That mode runs top-level statements in order, so there is no main:

@mode(web.scripted)

from system.collections import (zip, find, groupBy, sum, countWhere);

let names = ["Ana", "Ben", "Cy"];
let scores = [91, 78, 85];
for ((name, score) in zip(names, scores)) {
    println(i"{$ name $}: {$ score $}");
}
println(sum(scores));
println(countWhere(scores, func(s: int) => s >= 80));
println(repr(find(names, func(n: string) => n.starts_with("B"))));
println(groupBy(names, func(n: string) => n.char_at(0)));

Listing 6-7: system.collections helpers in a web.scripted file

Ana: 91
Ben: 78
Cy: 85
254
2
Some("Ben")
{"A": ["Ana"], "B": ["Ben"], "C": ["Cy"]}

dict[K, V]

A dict maps keys to values and remembers insertion order: keys(), values(), entries() and for (k in d) all visit entries in the order they were added (Language Reference §1-4.1.5).

@mode(web.compiled)

func main(): void {
    var stock: dict[string, int] = {"apples": 3, "bananas": 7};
    stock["cherries"] = 12;
    stock.set("dates", 5);
    println(stock);

    println(stock["apples"]);
    match stock.get("grapes") {
        Some(n) => println(i"{$ n $} grapes"),
        None => println("no grapes"),
    }
    println(stock.get("grapes") ?? 0);
    println(stock.contains("bananas"));

    let removed = stock.remove("bananas");
    println(removed ?? 0);
    println(stock.length());

    println(stock.keys());
    println(stock.values());
    for ((fruit, count) in stock.entries()) {
        println(i"{$ fruit $}: {$ count $}");
    }
}

Listing 6-8: Dict operations

{"apples": 3, "bananas": 7, "cherries": 12, "dates": 5}
3
no grapes
0
true
7
3
["apples", "cherries", "dates"]
[3, 12, 5]
apples: 3
cherries: 12
dates: 5

There are two ways to read a value, and they differ on a missing key. d[key] raises KeyError; d.get(key) returns an Option[V] (Chapter 8):

@mode(web.compiled)

func main(): void {
    let stock = {"apples": 3};
    println(stock["kiwis"]);
}

Uncaught KeyError: key 'kiwis' not found in dict
  at main (main.lpweb:5:13)

Use d[key] when a missing key is a bug, and d.get(key) ?? default or d.contains(key) when it is expected. The word counter below relies on ?? 0:

@mode(web.compiled)

func countWords(text: string): dict[string, int] {
    var counts: dict[string, int] = {};
    for (word in text.to_lowercase().split(" ")) {
        if (word == "") {
            continue;
        }
        counts[word] = (counts.get(word) ?? 0) + 1;
    }
    return counts;
}

func main(): void {
    let counts = countWords("The cat and the hat and the bat");
    println(counts);
    for ((word, n) in counts.entries()) {
        if (n > 1) {
            println(i"{$ word $} appears {$ n $} times");
        }
    }
}

Listing 6-9: A word counter

{"the": 3, "cat": 1, "and": 2, "hat": 1, "bat": 1}
the appears 3 times
and appears 2 times

A key type must be hashable. Primitives, strings, tuples, and structs and enums built from hashable parts qualify; a class does only if it implements Hashable (Chapter 10).

set[T]

A set holds unique values. Adding a value that is already present does nothing.

@mode(web.compiled)

func main(): void {
    var tags: set[string] = {"sale", "new"};
    tags.add("clearance");
    tags.add("sale");
    tags.remove("new");
    println(tags);
    println(tags.length());
    println(tags.contains("sale"));

    let none: set[int] = {};
    println(none.length());
}

Listing 6-10: Set operations

{"sale", "clearance"}
2
true
0

An empty {} is a dict unless the annotation says otherwise, which is why none is declared set[int]. The Language Reference leaves a set's iteration order to the implementation, so do not depend on it.

Sets have add, remove, contains, length() and to_string(), and nothing else in 1.25.1: there are no union or intersect methods and no | or & operators on sets. Write the loop (the function is not called shared, because shared is a reserved word):

@mode(web.compiled)

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

func main(): void {
    let postA: set[string] = {"loup", "wasm", "web"};
    let postB: set[string] = {"web", "css", "loup"};
    println(commonTags(postA, postB));
}

Listing 6-11: Intersecting two sets by hand

{"loup", "web"}

Tuples

A tuple is a fixed-size group of values whose types may differ. The type is written (int, string) or tuple[int, string]. Elements are read with .0, .1, …, or unpacked with destructuring:

@mode(web.compiled)

func divmod(a: int, b: int): (int, int) {
    return (a // b, a % b);
}

func lowHigh(xs: list[int]): tuple[int, int] {
    var lo = xs[0];
    var hi = xs[0];
    for (x in xs) {
        if (x < lo) { lo = x; }
        if (x > hi) { hi = x; }
    }
    return (lo, hi);
}

func main(): void {
    let entry: (string, int) = ("Ana", 91);
    println(entry.0);
    println(entry.1);

    let (q, r) = divmod(17, 5);
    println(i"{$ q $} remainder {$ r $}");

    let (lo, hi) = lowHigh([4, 9, 1, 7]);
    println(i"range {$ lo $} to {$ hi $}");

    println(("Ana", 91) == ("Ana", 91));
}

Listing 6-12: Tuples and destructuring

Ana
91
3 remainder 2
range 1 to 9
true

Tuples compare structurally, element by element. Destructuring also works in for headers (for ((name, score) in pairs)) and in match patterns (Chapter 5). When a tuple grows past two or three fields, or you keep forgetting which position means what, promote it to a struct with named fields (Chapter 7).

Collections are values

Assignment copies

Built collections are independent values (rulings COLL-1 and COLL-2). Assigning a list to another variable, or storing it somewhere, makes a copy; changing one does not change the other. This is the opposite of JavaScript arrays and Python lists:

@mode(web.compiled)

func main(): void {
    var saved = [1, 2, 3];
    var draft = saved;
    draft.push(4);
    println(saved);
    println(draft);

    var backup = saved.clone();
    backup.push(99);
    println(saved);
    println(backup);
}

Listing 6-13: Assigning a list copies it

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

clone() is still useful to make the copy explicit, but plain assignment already gives you one.

Passing a collection to a function

A parameter without an ownership verb is a read-only reads borrow (Chapter 9 and Chapter 20). A function that tries to change such a parameter is rejected:

@mode(web.compiled)

func addFreeGift(cart: list[string]): void {
    cart.push("sticker");
}

func main(): void {
    var cart = ["milk"];
    addFreeGift(cart);
    println(cart);
}

main.lpweb:4:5: error[E_READS_MUTATION]: E_READS_MUTATION: parameter 'cart' 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 gives both fixes. To change the caller's list, mark the parameter edits. The call site must then say edits: too, so a reader can see that the call changes cart. Leaving it out is its own error:

@mode(web.compiled)

func addFreeGift(edits cart: list[string]): void {
    cart.push("sticker");
}

func main(): void {
    var cart = ["milk"];
    addFreeGift(cart);
    println(cart);
}

main.lpweb:9:17: error[E_VERB_REQUIRED]: E_VERB_REQUIRED: parameter 'cart' requires 'edits' verb acknowledgment at call site

With both halves in place:

@mode(web.compiled)

func addFreeGift(edits cart: list[string]): void {
    cart.push("sticker");
}

func main(): void {
    var cart = ["milk"];
    addFreeGift(edits: cart);
    println(cart);
}

Listing 6-14: An edits parameter

["milk", "sticker"]

Comparing collections

Ruling EQ-3 says that == on lists, dicts and sets compares their elements. Loup 1.25.1 does not implement that yet: == on two separately built collections is false even when their contents match. This test looks right and gives the wrong answer:

@mode(web.compiled)

func main(): void {
    let expected = [1, 2, 3];
    let actual = [1, 2, 3];
    if (expected == actual) {
        println("match");
    } else {
        println("mismatch");
    }
}

mismatch

Until EQ-3 lands, compare element by element:

@mode(web.compiled)

func sameItems(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;
}

func main(): void {
    let expected = [1, 2, 3];
    let actual = [1, 2, 3];
    if (sameItems(expected, actual)) {
        println("match");
    } else {
        println("mismatch");
    }
}

Listing 6-15: Element-wise list comparison

match

Tuples, structs and enums already compare structurally.

Summary

• list[T] is ordered and indexable, with negative indexes from the end and colon slices xs[a:b]. Out-of-range access raises IndexError. Length is xs.length().
• The list method set is fixed and small; sort needs a comparator. Lambda parameters need type annotations.
• List comprehensions are [expr for x in xs if cond], without parentheses. Set and dict comprehensions are specified but not implemented yet.
• dict[K, V] keeps insertion order. d[k] raises KeyError for a missing key; d.get(k) returns an Option, usually paired with ??.
• set[T] has add, remove, contains and length(); write set algebra with a loop.
• Tuples group a few values, destructure with let (a, b) = …, and compare structurally.
• Assigning or storing a collection copies it. A parameter is read-only unless declared edits, and the caller must write edits:.
• == on collections is not element-wise in 1.25.1; compare contents yourself.
• system.collections (zip, find, groupBy, sum, …) is importable from web.scripted files but not from web.compiled files.