Generics

Functions, structs and enums can take type parameters in square brackets: fn first[T](xs: [T]) -> Option[T]. Each use with new type arguments makes a specialized copy of the code (monomorphization), which is checked, proven and compiled like hand-written code, so generics cost nothing at run time.

Generic functions

fn first[T](xs: [T]) -> Option[T]:
    if len(xs) == 0:
        return None
    return Some(xs[0])

fn swap[A, B](p: (A, B)) -> (B, A):
    return (p.1, p.0)

fn main():
    print(first([3, 4]), first(["a", "b"]))
    print(swap((1, "one")))
    let empty: [float] = []
    print(first(empty))
    print(first[int]([]))

Output

Some(3) Some("a")
("one", 1)
None
None

Type parameters go in brackets after the name, and can be used anywhere a type can in the signature and the body.

Generic structs and enums

struct Pair[A, B]:
    first: A
    second: B

    fn swapped(self) -> Pair[B, A]:
        return Pair(first=self.second, second=self.first)

enum Tree[T]:
    Leaf
    Node(left: Tree[T], value: T, right: Tree[T])

fn count[T](t: Tree[T]) -> int:
    match t:
        case Tree.Leaf:
            return 0
        case Tree.Node(l, _, r):
            return count(l) + 1 + count(r)

fn main():
    let p = Pair(first=1, second="one")              # Pair[int, str], inferred
    let q = Pair[int, str](first=2, second="two")    # written out
    print(p, q, p.swapped())
    let t = Tree.Node(Tree.Leaf, "m", Tree.Node(Tree.Leaf, "z", Tree.Leaf))
    print(count(t))
    let none: Option[int] = None
    var stack: [Pair[str, int]] = []
    stack.push(Pair("x", 1))
    print(none, stack)

Output

Pair(first=1, second="one") Pair(first=2, second="two") Pair(first="one", second=1)
2
None [Pair(first="x", second=1)]

In a type, write the arguments in brackets: Pair[str, int], [Pair[str, int]], Option[int]. The built-in Option[T] and Result[T, E] are generic enums like Tree[T].

Inference and explicit type arguments

Type arguments are inferred from the arguments and from the type the context expects. When neither says what a type parameter is, write it out after the name: make[int](), Pair[int, str](...), first[int]([]).

fn make[T]() -> [T]:
    return []

fn main():
    let xs = make()
    print(xs)

error[E0332]: can't infer type parameter `T` of `make`
 --> main.br:5:14
  |
5 |     let xs = make()
  |              ^^^^^^ type unknown here
  |
  = help: give the type explicitly, e.g. `make[int](...)`
  = run `brine explain E0332` for more about this error
error: could not compile due to 1 error

Here let xs: [int] = make() works too, because the annotation is the expected type. The same goes for None on its own: let n: Option[int] = None.

Each type parameter stands for one type, so fn same[T](a: T, b: T) called as same(1, "one") is a type mismatch (E0301).

Methods with their own type parameters

A method can have type parameters of its own, next to its type’s:

struct Box[T]:
    v: T

    fn pair[U](self, u: U) -> (T, U):
        return (self.v, u)

fn main():
    let b = Box(v=1)
    print(b.pair("x"), b.pair[float](2.5))

Output

(1, "x") (1, 2.5)

b.pair[float](2.5) gives U explicitly; 2.5 alone would also have inferred it.

Monomorphization: checked per use

There are no interfaces or trait bounds to declare. Instead, a generic function’s body is checked again for each set of type arguments it’s used with. largest compares with >, so it works for any type that supports >:

fn largest[T](xs: [T]) -> T:
    var best = xs[0]
    for x in xs:
        if x > best:
            best = x
    return best

fn main():
    print(largest([3, 9, 2]))
    print(largest(["pear", "apple", "fig"]))
    print(largest([1.5, -0.5]))

Output

9
pear
1.5

Using it with a struct, which can’t be ordered, is an error in the body, with a note saying which use caused it:

struct Point:
    x: int
    y: int

fn largest[T](xs: [T]) -> T:
    var best = xs[0]
    for x in xs:
        if x > best:
            best = x
    return best

fn main():
    print(largest([3, 9, 2]))
    print(largest([Point(1, 2), Point(3, 4)]))

error[E0305]: values of type `Point` can't be ordered
 --> main.br:8:12
  |
8 |         if x > best:
  |            ^^^^^^^^ only numbers and strings support `<`
  |
  = note: in `largest` with T = Point
  = run `brine explain E0305` for more about this error
error: could not compile due to 1 error

Each specialized copy is also proven like ordinary code: a generic function can carry contracts (requires len(xs) > 0), and every call must satisfy them.

Note

Because bodies are checked per use, a generic function that nothing calls isn’t checked at all in Brine 0.4.0, not even for unknown names. Call new generic code from a test to make sure it compiles.

Summary

• Type parameters in brackets: fn f[T](x: T), struct Pair[A, B], enum Tree[T], and on methods: fn pair[U](self, u: U).
• Type arguments are inferred from arguments and the expected type, or written out: make[int](), Pair[int, str](...).
• Each new set of type arguments makes a specialized copy, checked and proven like ordinary code. Operations a type doesn’t support are errors at that use.