# Chapter 11: Generics

**What you'll learn.** How to write functions, structs, classes, enums, and interfaces that take type parameters; how type arguments are inferred and when you must write them; how `where` clauses and bounds restrict a type parameter; and which parts of the generics design Loup 1.25.1 does not implement yet.

**Why it matters.** A web app is full of code that is the same for every element type: a cache of avatars and a cache of API responses, a "loading / ready / failed" state for a profile and for a feed. Generics let you write that code once and keep the element type checked at every use.

A generic declaration has one or more **type parameters** in square brackets after its name. At each use the type parameters are replaced by concrete **type arguments**, usually inferred from the values you pass. Loup uses square brackets where TypeScript, Rust, and Java use angle brackets: `list[int]`, `dict[string, User]`, `Option[T]`.

## Generic functions

Listing 11-1 declares three generic functions and calls them with different types.

```loup
@mode(web.compiled)

func identity[T](value: T): T {
    return value;
}

func swap[A, B](pair: (A, B)): (B, A) {
    return (pair.1, pair.0);
}

func firstOr[T](items: list[T], fallback: T): T {
    if (items.len() == 0) {
        return fallback;
    }
    return items[0];
}

func main(): void {
    println(identity(42));
    println(identity("hello"));
    println(swap(("port", 8080)));
    println(firstOr([3, 1, 2], 0));
    let empty: list[string] = [];
    println(firstOr(empty, "none"));
    println(identity[int](7));
}
```

*Listing 11-1: Generic functions, called with inferred and explicit type arguments*

```text
42
hello
(8080, "port")
3
none
7
```

`T`, `A`, and `B` can appear anywhere a type can: in parameters, in the return type, in local annotations, and inside other types such as `list[T]` or `(A, B)`. At each call the compiler matches the parameter types against the argument types to decide what `T` is: in `firstOr([3, 1, 2], 0)` both arguments say `T = int`. You can also write the type arguments yourself, in brackets right before the argument list: `identity[int](7)`.

### When inference cannot decide

Inference needs every argument to agree. Here the two arguments of `pair` say different things about `T`:

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

func pair[T](first: T, second: T): list[T] {
    return [first, second];
}

func main(): void {
    let widths = pair(320, 480.5);
    println(widths);
}
```

```text
main.lpweb:8:23: error[E0001]: argument 1 of 'pair': expected 'T0', found 'int'
main.lpweb:8:28: error[E0001]: argument 2 of 'pair': expected 'T0', found 'float'
```

`T0` is the compiler's name for the type parameter it could not pin down. Because `320` is an `int` and `480.5` is a `float`, `T` is constrained by two different types, and the Language Reference (§1-4.8, ruling GEN-1) makes that an error instead of picking one. Loup never converts between `int` and `float` silently (Chapter 3), so the fix is to make the arguments agree:

```loup
#~ @mode(web.compiled)
#~
#~ func pair[T](first: T, second: T): list[T] {
#~     return [first, second];
#~ }
#~
#~ func main(): void {
let widths = pair(320.0, 480.5);
println(widths);
#~ }
```

```text
[320.0, 480.5]
```

The opposite problem is a type parameter that no argument mentions. `emptyList` below takes no arguments, so nothing tells the compiler what `T` is, and an annotation on the receiving variable does not count:

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

func emptyList[T](): list[T] {
    return [];
}

func main(): void {
    let names: list[string] = emptyList();
    println(names.len());
}
```

```text
main.lpweb:8:5: error[E0001]: cannot assign 'list[T0]' to binding 'names' of type 'list[string]'
```

The call stays generic (`list[T0]`), and a generic list is not a `list[string]`. Supply the type argument at the call:

```loup
#~ @mode(web.compiled)
#~
#~ func emptyList[T](): list[T] {
#~     return [];
#~ }
#~
#~ func main(): void {
var names = emptyList[string]();
names.push("ada");
println(names);
#~ }
```

```text
["ada"]
```

Supplying the wrong number of type arguments is also caught: `emptyList[int, string]()` reports `function 'emptyList' expects 1 type argument(s), but 2 provided`.

## Generic structs, classes, and enums

Type declarations take type parameters the same way. Listing 11-2 shows one of each: a `Range[T]` value type, an undo `Stack[T]` class, and a `Loadable[T]` enum for data that is still being fetched.

```loup
@mode(web.compiled)

struct Range[T] {
    low: T;
    high: T;
}

class Stack[T] {
    var items: list[T] = [];

    pub modifier func push(item: T): void {
        this.items.push(item);
    }

    pub modifier func pop(): Option[T] {
        if (this.items.len() == 0) {
            return None;
        }
        return Some(this.items.pop());
    }

    pub func size(): int {
        return this.items.len();
    }
}

enum Loadable[T] {
    Loading,
    Ready(value: T),
    Failed(reason: string),
}

func main(): void {
    let ages = Range(low = 13, high = 120);
    let letters: Range[string] = Range(low = "a", high = "m");
    println(ages);
    println(letters.high);

    let undo: Stack[string] = Stack();
    safe {
        undo.push("type 'a'");
        undo.push("type 'b'");
        println(undo.pop().unwrap_or("nothing"));
    }
    println(undo.size());

    let unread: Loadable[int] = Loadable.Ready(value = 3);
    match unread {
        Loadable.Loading => println("loading"),
        Loadable.Ready(value) => println(i"{$ value $} unread messages"),
        Loadable.Failed(reason) => println(i"failed: {$ reason $}"),
    }
}
```

*Listing 11-2: A generic struct, class, and enum*

```text
Range(low: 13, high: 120)
m
type 'b'
1
3 unread messages
```

`Range(low = 13, high = 120)` infers `T = int` from the field values. `Stack()` has no arguments to infer from, so the binding's annotation `Stack[string]` supplies `T`. Inside the class, `T` is used in field types, parameters, and return types, and every method is checked once against the unknown `T`.

> ⚠ **Known gap.** The Language Reference (§1-4.8) also lets you write the type argument on the constructor call: `let undo = Stack[string]();`. Loup 1.25.1 accepts that line but does not specialise the methods, so the first `undo.push("…")` is rejected with `argument 1 of 'push': expected 'T0', found 'string'`. Until this is fixed, put the type on the binding as Listing 11-2 does.

## Bounds and `where` clauses

An unconstrained `T` supports almost nothing: you can store it, return it, and pass it to other generic code. To compare two `T` values, or use one as a dictionary key, you need a **bound**: a requirement that `T` implements an interface. The standard interfaces you will bound on most are `Comparable[T]` (ordering with `<`, `>`, `<=`, `>=`, through a `compareTo(other: T): int` method) and `Hashable` (a `hashCode(): int` method, required for `dict` keys and `set` elements). They are listed in Language Reference §1-11.2.

For a generic function, write the bound in a `where` clause after the return type. Listing 11-3 finds the newest release in a list; it works for `int` (which is `Comparable` built in) and for a `Version` class that implements `Comparable[Version]` itself.

```loup
@mode(web.compiled)

class Version implements Comparable[Version] {
    pub let major: int;
    pub let minor: int;

    new(major: int, minor: int) {
        this.major = major;
        this.minor = minor;
    }

    pub func compareTo(other: Version): int {
        if (this.major != other.major) {
            return this.major - other.major;
        }
        return this.minor - other.minor;
    }
}

func newest[T](items: list[T]): T where T: Comparable[T] {
    var best = items[0];
    for (item in items) {
        if (item > best) {
            best = item;
        }
    }
    return best;
}

func main(): void {
    println(Version(1, 2) < Version(1, 10));
    let v = newest([Version(1, 2), Version(2, 0), Version(1, 10)]);
    println(i"{$ v.major $}.{$ v.minor $}");
    println(newest([3, 9, 4]));
}
```

*Listing 11-3: A `where` clause lets the body compare `T` values*

```text
true
2.0
9
```

`item > best` compiles because the bound promises `compareTo`: the comparison operators desugar to `a.compareTo(b) > 0` and friends (Language Reference §1-5.1). Several bounds are joined with `+`, as in `where T: Comparable[T] + Hashable`, and several parameters are separated by commas.

### Writing the bound inside the brackets

The Language Reference treats `func newest[T: Comparable[T]](…)` and `func newest[T](…) where T: Comparable[T]` as the same declaration. In Loup 1.25.1 they are not: a bound written inside the brackets of a *function* is not visible in its body.

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

func newest[T: Comparable[T]](items: list[T]): T {
    var best = items[0];
    for (item in items) {
        if (item > best) {
            best = item;
        }
    }
    return best;
}

func main(): void {
    println(newest([3, 9, 4]));
}
```

```text
main.lpweb:6:13: error[E0001]: type 'T0' has no method 'compareTo'
```

The message says that inside the body the checker knows nothing about `T`, so `>` (which needs `compareTo`) is unavailable. Move the bound to a `where` clause, as in Listing 11-3. The same limitation applies to the methods of a generic class: a class written `class Leaderboard[T: Comparable[T]]` cannot use `>` on `T` in its own methods today, and a `where` clause on a class is not parsed. Keep the comparison in a `where`-bounded free function and call it from the method:

```loup
@mode(web.compiled)

func newest[T](items: list[T]): T where T: Comparable[T] {
    var best = items[0];
    for (item in items) {
        if (item > best) {
            best = item;
        }
    }
    return best;
}

class Leaderboard[T: Comparable[T]] {
    var scores: list[T] = [];

    pub modifier func add(score: T): void {
        this.scores.push(score);
    }

    pub func best(): Option[T] {
        if (this.scores.len() == 0) {
            return None;
        }
        return Some(newest(this.scores));
    }
}

func main(): void {
    let board: Leaderboard[int] = Leaderboard();
    println(repr(board.best()));
    safe {
        board.add(120);
        board.add(340);
        board.add(95);
    }
    println(repr(board.best()));
}
```

*Listing 11-4: A bounded generic class that delegates its comparison to a `where`-bounded function*

```text
None
Some(340)
```

### Bounds on a generic type are checked where you use the type

A bound inside the brackets of a class, struct, or enum *is* enforced: every time you name the type with concrete arguments, the compiler checks them. Here a cache keyed by a `Session` object fails because `Session` is not `Hashable`:

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

class Cache[K: Hashable, V] {
    var entries: dict[K, V] = {};
}

class Session {
    pub let token: string;
    new(token: string) { this.token = token; }
}

func main(): void {
    let bySession: Cache[Session, int] = Cache();
    println("created");
}
```

```text
main.lpweb:13:20: error[E_GENERIC_BOUND_UNSATISFIED]: E_GENERIC_BOUND_UNSATISFIED: Session does not implement 'Hashable', required by type parameter 'K' of 'Cache'
```

The fix depends on what you meant. Usually the identity of a session is its token, so key the cache by the token string, which is `Hashable` built in:

```loup
@mode(web.compiled)

class Cache[K: Hashable, V] {
    var entries: dict[K, V] = {};
}

class Session {
    pub let token: string;
    new(token: string) { this.token = token; }
}

func main(): void {
    let session = Session("a1b2");
    let bySession: Cache[string, int] = Cache();
    println(i"cache ready for {$ session.token $}");
}
```

```text
cache ready for a1b2
```

The other option is to make `Session` implement `Hashable` by giving it a `pub func hashCode(): int` method.

### Function bounds are not checked at the call site yet

The Language Reference requires the compiler to reject a call whose type argument does not satisfy a function's bound (`E_GENERIC_BOUND_UNSATISFIED`, `E_WHERE_BOUND_NOT_MET`). Loup 1.25.1 does not check this for functions, in either form. The call compiles, and the program fails when the body uses the missing method:

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

interface Named {
    func name(): string;
}

func names[T](items: list[T]): list[string] where T: Named {
    var out: list[string] = [];
    for (item in items) {
        out.push(item.name());
    }
    return out;
}

func main(): void {
    println(names([1, 2, 3]));
}
```

```text
Uncaught RuntimeError: internal interpreter limitation: unsupported instruction: CallVirtual name on Int(1)
```

Until the check exists, treat a `where` clause as a promise you keep yourself, and test generic functions with the types you call them with.

## Printing a value of a type parameter

A natural first generic helper describes a value. In Loup 1.25.1 an unconstrained `T` cannot be passed to `println`, `str`, `repr`, or an `i"…"` interpolation:

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

enum Loadable[T] {
    Loading,
    Ready(value: T),
    Failed(reason: string),
}

func describe[T](state: Loadable[T]): string {
    return match state {
        Loadable.Loading => "loading…",
        Loadable.Ready(value) => i"ready: {$ value $}",
        Loadable.Failed(reason) => i"failed: {$ reason $}",
    };
}

func main(): void {
    let profile: Loadable[string] = Loadable.Ready(value = "ada");
    println(describe(profile));
}
```

```text
main.lpweb:12:46: error[E0001]: argument 1 of '__render': expected 'Any', found 'T0'
```

`__render` is the function that interpolation calls; it takes `Any`, and the checker does not widen a type parameter to `Any`. The robust fix is the one you would use in TypeScript or Rust anyway: let the caller say how to show a `T`, by passing a function.

```loup
@mode(web.compiled)

enum Loadable[T] {
    Loading,
    Ready(value: T),
    Failed(reason: string),
}

func describe[T](state: Loadable[T], show: fn(T): string): string {
    return match state {
        Loadable.Loading => "loading…",
        Loadable.Ready(value) => i"ready: {$ show(value) $}",
        Loadable.Failed(reason) => i"failed: {$ reason $}",
    };
}

func main(): void {
    let profile: Loadable[string] = Loadable.Ready(value = "ada");
    let unread: Loadable[int] = Loadable.Ready(value = 3);
    let feed: Loadable[int] = Loadable.Failed(reason = "timeout");
    let pending: Loadable[int] = Loadable.Loading;
    println(describe(profile, func(name: string): string => name.to_uppercase()));
    println(describe(unread, func(n: int): string => i"{$ n $} unread"));
    println(describe(feed, func(n: int): string => str(n)));
    println(describe(pending, func(n: int): string => str(n)));
}
```

*Listing 11-5: Passing a formatting function instead of rendering `T` directly*

```text
ready: ADA
ready: 3 unread
failed: timeout
loading…
```

The function type `fn(T): string` is itself generic: at each call `T` is fixed by the `Loadable` argument, and the lambda must match.

## Generic interfaces and higher-order helpers

Interfaces take type parameters too. A class can implement a generic interface at a concrete type argument:

```loup
@mode(web.compiled)

interface Store[T] {
    func get(key: string): Option[T];
}

class ThemeStore implements Store[string] {
    var data: dict[string, string] = {"ada": "dark"};

    pub func get(key: string): Option[string] {
        if (this.data.contains_key(key)) {
            return Some(this.data[key]);
        }
        return None;
    }
}

func main(): void {
    let themes = ThemeStore();
    println(repr(themes.get("ada")));
    println(repr(themes.get("lin")));
}
```

*Listing 11-6: Implementing a generic interface at a concrete type*

```text
Some("dark")
None
```

Functions with several type parameters are how you write higher-order helpers. `mapAll` turns a `list[T]` into a `list[U]`, with `U` inferred from the lambda's return type:

```loup
@mode(web.compiled)

func mapAll[T, U](items: list[T], f: fn(T): U): list[U] {
    var out: list[U] = [];
    for (item in items) {
        out.push(f(item));
    }
    return out;
}

func main(): void {
    let cents = [1999, 450];
    let labels = mapAll(cents, func(c: int): string => "$" + str(c // 100) + "." + str(c % 100));
    println(labels);
}
```

*Listing 11-7: A generic function with two type parameters*

```text
["$19.99", "$4.50"]
```

> ⚠ **Planned.** Two more forms from the Language Reference do not work in Loup 1.25.1. A generic class implementing a generic interface with its own parameter (`class MemoryStore[T] implements Store[T]`) is rejected with `undefined type 'T'`. A method that introduces its own type parameter (`func map[U](f: fn(T): U): list[U]` inside `class Batch[T]`) confuses `U` with `T` and rejects valid calls. Use a concrete type argument, as in Listing 11-6, or a free function like `mapAll`.

## Variance

Variance answers the question "if `Button` is a `Widget`, is a `list[Button]` a `list[Widget]`?". The Language Reference (§1-4.8) makes generic types invariant by default, with optional `out T` (covariant) and `in T` (contravariant) annotations, and lets the compiler infer variance where it can. The annotations are not parsed by Loup 1.25.1 (`class Feed[out T]` is a syntax error).

For the built-in collections the question has a simple answer today: a `list[Button]` is accepted where a `list[Widget]` is expected.

```loup
@mode(web.compiled)

class Widget {
    pub func label(): string { return "widget"; }
}

class Button : Widget {
    pub override func label(): string { return "button"; }
}

func labels(widgets: list[Widget]): list[string] {
    var out: list[string] = [];
    for (w in widgets) {
        out.push(w.label());
    }
    return out;
}

func main(): void {
    let buttons: list[Button] = [Button(), Button()];
    println(labels(buttons));
}
```

*Listing 11-8: Passing a `list[Button]` where a `list[Widget]` is expected*

```text
["button", "button"]
```

This is safe for built-in collections because assigning or passing one copies it (Chapter 6): code that receives `widgets` and pushes a plain `Widget` changes its own copy, not your `buttons`. Java's covariant arrays are unsafe precisely because they are shared.

## A worked example: a small LRU cache

Listing 11-9 is a least-recently-inserted cache you might put in front of avatar URLs or API responses. It has two type parameters, a `Hashable` bound on the key, and evicts the oldest key when it is full.

```loup
@mode(web.compiled)

class Cache[K: Hashable, V] {
    let capacity: int;
    var entries: dict[K, V] = {};
    var order: list[K] = [];

    new(capacity: int) {
        this.capacity = capacity;
    }

    pub func get(key: K): Option[V] {
        if (this.entries.contains_key(key)) {
            return Some(this.entries[key]);
        }
        return None;
    }

    pub modifier func put(key: K, value: V): void {
        if (not this.entries.contains_key(key)) {
            if (this.order.len() == this.capacity) {
                let oldest = this.order[0];
                this.order = this.order.slice(1, this.order.len());
                this.entries.remove(oldest);
            }
            this.order.push(key);
        }
        this.entries[key] = value;
    }

    pub func size(): int {
        return this.entries.len();
    }
}

func main(): void {
    let avatars: Cache[string, string] = Cache(3);
    safe {
        avatars.put("ada", "/img/ada.png");
        avatars.put("lin", "/img/lin.png");
        avatars.put("sam", "/img/sam.png");
        avatars.put("kim", "/img/kim.png");
    }
    println(avatars.size());
    println(repr(avatars.get("ada")));
    println(avatars.get("kim").unwrap_or("/img/default.png"));

    let hits: Cache[int, int] = Cache(2);
    safe { hits.put(404, 12); }
    println(hits.get(404).unwrap_or(0));
}
```

*Listing 11-9: A generic cache with a bounded key type*

```text
3
None
/img/kim.png
12
```

Inserting `"kim"` into the full cache evicted `"ada"`, the oldest key. The same class serves `Cache[string, string]` and `Cache[int, int]`; `Cache[Session, int]` would be rejected at the annotation because `Session` is not `Hashable`.

## Try it yourself

1. Add a `func clampTo[T](value: T, low: T, high: T): T where T: Comparable[T]` and call it with `int`s and with `float`s. Then call it as `clampTo(2.5, 0, 10)` and read the errors.
2. Give `Cache` a `func keys(): list[K]` method that returns the keys from oldest to newest.
3. Write `func countWhere[T](items: list[T], keep: fn(T): bool): int` and use it to count the failed requests in a `list[int]` of HTTP status codes.

## Summary

- Type parameters go in square brackets after the name: `func f[T]`, `struct Range[T]`, `class Stack[T]`, `enum Loadable[T]`, `interface Store[T]`.
- Type arguments are inferred from the arguments; write them explicitly (`emptyList[string]()`) when nothing constrains a parameter, and make arguments agree (`320.0`, not `320`) when two disagree.
- Bound a function's type parameter with a `where` clause (`where T: Comparable[T] + Hashable`). In Loup 1.25.1 an in-bracket bound on a function is not visible in its body, and function bounds are not checked at call sites.
- Bounds in the brackets of a generic *type* are checked wherever the type is named (`E_GENERIC_BOUND_UNSATISFIED`).
- An unconstrained `T` cannot be printed or interpolated today; pass a `fn(T): string` instead.
- Generic interfaces work at concrete type arguments; generic `implements Store[T]`, method-level type parameters, explicit constructor type arguments, and `out`/`in` variance annotations are not implemented yet.