Generics

A generic function uses a type variable to work with any type. Write the function once; the compiler creates a specialised copy for each concrete type you call it with.

Declaring a generic function

Place a type variable in angle brackets after the function name. The type variable must appear in a parameter (directly or as a container element like vector<T>) — any parameter; a T that appears only in the return type is refused, since a call infers T from its arguments. A header may declare several variables — <K: Printable, V: Printable> — each with its own bounds, each inferred from the parameters that name it.

A struct may declare type variables too — see Generic structs below.

fn identity<T>(x: T) -> T { x }

Calling a generic function

No special syntax at the call site — the compiler infers T from the arguments' types and creates a specialised copy automatically.

fn test_identity() {
  assert(identity(42) == 42, "identity integer");
  assert(identity(3.14) == 3.14, "identity float");
  assert(identity("hello") == "hello", "identity text");
  assert(identity(true) == true, "identity bool");
}

Multiple parameters of the same type

Additional parameters can also use T. They all share the same concrete type.

fn pick_second<T>(gen_a: T, gen_b: T) -> T {
  _x = gen_a;
  gen_b
}
fn test_pick_second() {
  assert(pick_second(1, 99) == 99, "pick second int");
  assert(pick_second("a", "b") == "b", "pick second text");
}

Generic functions on vectors

The most common use of generics: write a function that works on any vector. T is inferred from the vector's element type.

fn first_element<T>(gen_v: vector<T>) -> T {
  gen_v[0]
}

A computed index gen_v.len() - 1 is not provably in-bounds, so the read is nullable; a generic has no value of T of its own to write after ??, so the honest result type is T? (or take the fallback as a parameter: v[i] ?? d).

fn last_element<T>(gen_v: vector<T>) -> T? {
  gen_v[gen_v.len() - 1]
}
fn test_vector_generics() {
  ints = [10, 20, 30];
  assert(first_element(ints) == 10, "first int");
  assert(last_element(ints) == 30, "last int");
  words = ["alpha", "beta", "gamma"];
  assert(first_element(words) == "alpha", "first text");
  assert(last_element(words) == "gamma", "last text");

A CONSTANT index is trusted, and an empty vector is where that trust runs out: gen_v[0] is typed T and still answers null on an empty vector, so the null travels through a return type that says it cannot be there. Check the length before calling, or declare the result T? as last_element does and let the caller discharge it.

  empty: vector<integer> = [];
  assert(!first_element(empty), "`v[0]` on an empty vector is null despite the `T` return");
}

Bounded generics with interfaces

By default, you can only assign and return T — no arithmetic, and no comparison either: a == b on an unbounded T is refused. To use an operator on T, add an interface bound.

Each bound guarantees EXACTLY the operations in this table, and no more — a + under Numeric is refused as surely as one under no bound at all. Each names the FEWEST methods it needs, because the operators are derived: <, <=, > and >= all read compare, and != comes from ==.

Ordered    — declares `compare`; gives you `<`, `<=`, `>`, `>=`
Equatable  — declares nothing; every type has `==` and `!=`
Addable      — `+` only.  NOT `-`
Numeric      — `*` and the UNARY `-a`.  NOT `+`, NOT `/`
Subtractable — the BINARY `a - b`
Scalable   — the method `scale(self, factor: integer) -> integer`.  Not an
             operator, and no built-in type satisfies it — it is for your own types
Printable  — the method `to_text() -> text`, and `"{x}"` interpolation
Walkable   — the method `children() -> vector<Self>`.  The standard library's
             `tree_walk` is bounded by it, so defining `children` on your own
             type gets you a breadth-first walk without writing one

Reach for Ordered + Addable when you want + and a comparison.

- desugars to the same OpMin name at BOTH arities, so unary negation and binary subtraction are two SIGNATURES of one name — and therefore two bounds: <T: Numeric> gives you -a, <T: Subtractable> gives you a - b, and <T: Numeric + Subtractable> gives you both. A user type may declare OpMin at both arities, in either order: a - b reaches the binary one and -a the unary one, so it satisfies both bounds.

fn gen_diff<T: Subtractable>(gen_a: T, gen_b: T) -> T { gen_a - gen_b }
fn gen_negdiff<T: Numeric + Subtractable>(gen_a: T, gen_b: T) -> T { -(gen_a - gen_b) }
fn gen_max<T: Ordered>(gen_x: T, gen_y: T) -> T {
  if gen_x > gen_y { gen_x } else { gen_y }
}
fn gen_min<T: Ordered>(gen_x: T, gen_y: T) -> T {
  if gen_x < gen_y { gen_x } else { gen_y }
}
fn same<T: Equatable>(gen_x: T, gen_y: T) -> boolean {
  gen_x == gen_y
}
fn described<T: Printable>(gen_x: T) -> text {
  gen_x.to_text()
}
fn test_bounded() {
  assert(gen_max(3, 7) == 7, "max int");
  assert(gen_max(2.5, 1.5) == 2.5, "max float");
  assert(gen_min(3, 7) == 3, "min int");
  assert(gen_min("apple", "banana") == "apple", "min text");
  assert(gen_diff(10, 3) == 7, "subtraction under a bound");
  assert(gen_diff(2.5, 0.5) == 2.0, "subtraction under a bound, float");
  assert(gen_negdiff(10, 3) == -7, "both arities of `-` on one variable");
  assert(same(4, 4), "equatable on integers");
  assert(!same("a", "b"), "…and it says no as well");
  assert(described(7) == "7", "printable: {described(7)}");
}

Combining bounds

Use + to require multiple interfaces: <T: Ordered + Addable>.

fn clamped_add<T: Ordered + Addable>(gen_a: T, gen_b: T, gen_hi: T) -> T {
  result = gen_a + gen_b;
  if result > gen_hi { gen_hi } else { result }
}
fn test_combined_bounds() {
  assert(clamped_add(3, 4, 10) == 7, "under limit");
  assert(clamped_add(8, 5, 10) == 10, "clamped to limit");
  assert(clamped_add(1.0, 2.0, 2.5) == 2.5, "float clamped");
}

Your own types under a bound

The built-in bounds are not only for built-in types, and this is what they are for: a struct satisfies one by DEFINING the operation, with no declaration that it does. An operator is an operator method — written with the keyword operator where a function has fn — named for what it does:

Ordered      operator compare(self: T, other: T) -> Ordering   (`<` `<=` `>` `>=`)
Addable      operator plus(self: T, other: T) -> T            (`+`)
Subtractable operator minus(self: T, other: T) -> T           (binary `-`)
Numeric      operator times(self: T, other: T) -> T           (`*`)
             operator negate(self: T) -> T                    (unary `-`)
Scalable     fn scale(self: T, factor: integer) -> integer
Printable    operator to_text(self: T) -> text
Walkable     fn children(self: T) -> vector<T>

compare answers Less, Equal or Greater; every built-in ordered type has one, so self.cents.compare(other.cents) is the whole body for one field. Equatable is met by every type: == always compares what two values hold — a struct field by field — and no type can redefine it; a comparison of your own is a named method.

The same definition serves the bare operator: once Money has compare, both a < b and <T: Ordered> work on it. Miss one and the error names it — "Money does not satisfy interface Ordered: missing operator compare(self: Money, other: Money) -> Ordering" — at the CALL site, because that is where the concrete type is known.

struct Money { cents: integer }
operator compare(self: Money, other: Money) -> Ordering { self.cents.compare(other.cents) }
operator plus(self: Money, other: Money) -> Money { Money { cents: self.cents + other.cents } }
operator minus(self: Money, other: Money) -> Money { Money { cents: self.cents - other.cents } }
operator negate(self: Money) -> Money { Money { cents: 0 - self.cents } }
operator times(self: Money, other: Money) -> Money { Money { cents: self.cents * other.cents } }
operator to_text(self: Money) -> text { "{self.cents}c" }
fn test_user_type_bounds() {
  cheap = Money { cents: 300 };
  dear = Money { cents: 700 };
  best = gen_max(cheap, dear);
  assert(best.cents == 700, "Ordered on a user type: {best.cents}");
  assert(cheap < dear, "…and the bare operator, from the same definition");
  assert(same(cheap, Money { cents: 300 }), "Equatable on a user type");
  assert(same(Tile { height: 1, name: "t" }, Tile { height: 1, name: "t" }), "…and on one that defines no operator");
  assert(!same(Tile { height: 1, name: "t" }, Tile { height: 2, name: "t" }), "…comparing every field");
  total = clamped_add(cheap, cheap, Money { cents: 1000 });
  assert(total.cents == 600, "Addable on a user type: {total.cents}");
  assert(described(dear) == "700c", "Printable on a user type: {described(dear)}");
  assert(gen_diff(dear, cheap).cents == 400, "Subtractable on a user type");
  assert(gen_negdiff(dear, cheap).cents == -400, "Numeric + Subtractable on a user type");
}
struct Crate { label: text, kids: vector<Crate> }
fn children(self: Crate) -> vector<Crate> { self.kids }
fn test_walkable() {

children is the whole of what Walkable asks for; tree_walk is the stdlib's, bounded by it, and it visits the root before either child.

  tree = Crate { label: "root", kids: [
    Crate { label: "a", kids: [] },
    Crate { label: "b", kids: [] },
  ] };
  seen = "";
  for node in tree_walk(tree, 10) { seen += "{node.label} "; }
  assert(seen == "root a b ", "Walkable on a user type: {seen}");
}

Generic structs

A struct may declare type variables: struct Box<T> { v: T }. Box<integer> names an INSTANCE — an ordinary struct whose v is an integer, laid out as a hand-written struct BoxInteger { v: integer } would be. A literal builds the instance its annotation names, or else the one its field values bind: Box { v: 1 } is a Box<integer>, as identity(1) makes T an integer. A literal with nothing to bind a variable from (Box {}, Box { v: [] } for a vector<T> field) is refused, naming the variable; give the binding its type.

struct Box<T> { v: T }
struct Stack<T> { items: vector<T>, name: text }
fn twice(b: Box<integer>) -> integer { b.v * 2 }
fn test_generic_struct() {
  b = Box { v: 21 };
  t = Box { v: "hi" };
  s: Stack<float> = Stack { items: [], name: "floats" };
  s.items += [1.5, 2.5];
  assert(twice(b) == 42, "an inferred Box<integer> is the one the parameter names");
  assert(t.v == "hi" && len(s.items) == 2, "Box<text> and Stack<float>");
}

Two type variables and a callback

A generic may declare several variables, and one no argument binds may be bound by a callback's RESULT: map_grid below turns a Grid<T> into a Grid<U>, and the short lambda's body decides what U is — |t| { t.height } makes it an integer. A generic beside a concrete function of the same name is one overload set: the concrete show takes a Grid<Tile>, the bounded generic every other Grid it can print.

struct Tile { height: integer, name: text }
operator to_text(self: Tile) -> text { self.name }
struct Grid<T> { w: integer, cells: vector<T> }
fn map_grid<T, U>(g: Grid<T>, f: fn(T) -> U) -> Grid<U> {
  out: vector<U> = [];
  for c in g.cells { out += [f(c)]; }
  Grid { w: g.w, cells: out }
}
fn show<T: Printable>(g: Grid<T>) -> text { r = ""; for c in g.cells { r += "[{c.to_text()}]"; } r }
fn show(g: Grid<Tile>) -> text { "tiles:{len(g.cells)}" }
fn test_two_variables() {
  tiles = Grid { w: 2, cells: [Tile { height: 3, name: "a" }, Tile { height: 5, name: "b" }] };
  heights = map_grid(tiles, |t| { t.height });
  assert(show(tiles) == "tiles:2" && show(heights) == "[3][5]", "{show(heights)}");
}

Disallowed operations

The compiler rejects operations the bound does not cover, and it says which: x + y on unbounded T — "generic type T: operator + requires a concrete type" x.field on T — "generic type T: field access requires a concrete type" The same wording covers an operator OUTSIDE a bound: x + y under Numeric and x - y under Addable are refused in exactly those words.

fn main() {
  test_identity();
  test_pick_second();
  test_vector_generics();
  test_bounded();
  test_combined_bounds();
  test_user_type_bounds();
  test_walkable();
  test_generic_struct();
  test_two_variables();
}