# 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

| Type | What it stores | You reach it by |
|---|---|---|
| `list[T]` | an ordered sequence of `T` | position: `xs[0]` |
| `dict[K, V]` | a map from keys `K` to values `V`, in insertion order | key: `d["host"]` |
| `set[T]` | unique `T` values | membership: `x in s` |
| `tuple[A, B, …]` (also written `(A, B, …)`) | a fixed number of values of possibly different types | position: `t.0`, or destructuring |

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:

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

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

```loup
#~ @mode(host.scripted)
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());
```

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

```loup,throws
#~ @mode(host.scripted)
let scores = [88, 72, 95];
println(scores[3]);
```

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

```loup
#~ @mode(host.scripted)
let scores = [88, 72, 95];
let wanted = 3;

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

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

```loup
#~ @mode(host.scripted)
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*

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

```loup
#~ @mode(host.scripted)
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*

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

```loup
#~ @mode(host.scripted)
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*

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

```loup,does_not_compile
@mode(host.scripted)

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

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

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

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

```loup
#~ @mode(host.scripted)
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*

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

```loup,does_not_compile
@mode(host.scripted)

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

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

```loup
@mode(host.scripted)

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

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

```loup
#~ @mode(host.scripted)
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*

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

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

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

```loup,throws
#~ @mode(host.scripted)
let ports = {"http": 80, "https": 443};
println(ports["ssh"]);
```

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

```loup
#~ @mode(host.scripted)
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");
}
```

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

```loup,does_not_compile
@mode(host.scripted)

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

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

```loup
@mode(host.scripted)

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

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

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

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

```loup
#~ @mode(host.scripted)
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));
```

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

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

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

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

```loup
#~ @mode(host.scripted)
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 $}");
```

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

```loup
#~ @mode(host.scripted)
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);
```

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

```loup
#~ @mode(host.scripted)
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]);
```

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

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

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

```loup,does_not_compile
@mode(host.scripted)

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

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

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

```loup
@mode(host.scripted)

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

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

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

```loup,not_desired_behavior
@mode(host.scripted)

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

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

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

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

```loup,not_desired_behavior
#~ @mode(host.scripted)
let expected = [1, 2, 3];
let actual = [1, 2, 3];
println(expected == actual);
```

```text
false
```

A small helper does the element-wise comparison:

```loup
#~ @mode(host.scripted)
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]));
```

```text
true
false
```

Tuples, structs and enums already compare by value.

## Practical Example: Word Frequencies

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

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