# 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.

```loup
@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*

```text
["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:

```loup,does_not_compile
@mode(web.compiled)

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

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

```loup,does_not_compile
@mode(web.compiled)

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

```text
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`:

```loup,throws
@mode(web.compiled)

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

```text
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:

```loup
@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*

```text
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.

```loup
@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*

```text
[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:

```loup,does_not_compile
@mode(web.compiled)

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

```text
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):

```loup
@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*

```text
[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:

```loup,does_not_compile
@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);
}
```

```text
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`.

```loup
@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*

```text
[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:

```loup,does_not_compile
@mode(web.compiled)

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

```text
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:

```loup,does_not_compile
@mode(web.compiled)

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

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

Pass the comparison you want:

```loup
@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*

```text
["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](ch02-compiled-mode-rules.md)):

```loup,does_not_compile
@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 $}");
    }
}
```

```text
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`:

```loup
@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*

```text
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).

```loup
@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*

```text
{"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):

```loup,throws
@mode(web.compiled)

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

```text
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`:

```loup
@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*

```text
{"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.

```loup
@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*

```text
{"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):

```loup
@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*

```text
{"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:

```loup
@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*

```text
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:

```loup
@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*

```text
[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:

```loup,does_not_compile
@mode(web.compiled)

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

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

```text
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:

```loup,does_not_compile
@mode(web.compiled)

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

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

```text
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:

```loup
@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*

```text
["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:

```loup,not_desired_behavior
@mode(web.compiled)

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

```text
mismatch
```

Until EQ-3 lands, compare element by element:

```loup
@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*

```text
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.