Generics

A generic is code written once against a type it does not know, and a bound is what it is allowed to assume about that type. Everything below is one of those two things.

Type parameters on functions

fn identity<A>(value: A) -> A {
  value
}

Several parameters:

fn pair<A, B>(left: A, right: B) -> (A, B) {
  (left, right)
}

General parameter-list shape:

<Name, Name, ...>

Type parameters on data types

pub type Box<A> = {
  value: A,
};

pub type Result<A, E> =
  | Ok(value: A)
  | Err(error: E);

Generic type arguments

Box<Int>
Result<User, DbError>
Map<String, User>

<...> in type position is always a type-argument list; no turbofish syntax is required.

Trait bounds

Single bound:

fn same<A: Eq>(left: A, right: A) -> Bool {
  left == right
}

Several bounds:

fn render<A: Eq + Show>(value: A) -> String {
  Show::show(value)
}

General form:

A: Trait + OtherTrait

Each bound is a trait path. Ask for the smallest useful one: a function that needs only equality should bound on Eq and not on something broader, because the bound is what a caller has to satisfy.

Const generic parameters

pub type Matrix<A, const Rows: Int, const Cols: Int>;

General form:

const Name: Type

Integer literals can be supplied as type arguments:

Matrix<Float, 4, 4>
Embedding<1536>

A const generic is part of a type’s compile-time identity; it is distinct from a module-level const declaration.

Row-variable parameters

fn call<A, B, 'ef, 'er>(
  value: A,
  f: A -> B with 'ef raises 'er,
) -> B
  with 'ef
  raises 'er
{
  f(value)!
}

A row variable is introduced directly in the generic parameter list:

'ef
'er

Its spelling is arbitrary; the position where it is used determines whether it represents capability requirements, failures, or another row-shaped type.

This is why an effectful or fallible function can be handed to an ordinary higher-order operation without a separate traverse-shaped API beside it: the combinator is polymorphic in the rows its argument carries, and passes them through to its own signature.

Open record/capability rows

{ db: Db | 'ef }

The named entries are required and the row variable represents any additional entries.

Higher-kinded use

A generic parameter can be used as a type constructor when its use requires that kind:

fn construct<F, A>(value: A, make: A -> F<A>) -> F<A> {
  make(value)
}

Here F is used with one type argument, so it is a type constructor rather than an inhabited concrete type. Kinds are checked from how parameters are used; Khora does not require a separate source-level kind annotation on this declaration.

Explicit forall

A type value can quantify its own parameters:

forall<A>. A -> A

Several parameters:

forall<A, B>. (A, B) -> (B, A)

Const parameter:

forall<A, const N: Int>. A -> Vector<A>

General form:

forall<TypeParams>. Type

Named generic declarations introduce their parameters directly and usually do not need explicit forall. It earns its place in an API that stores or accepts a polymorphic function value, where there is no declaration to hang the parameter on.

A forall value cannot be called yet

This is a gap in the compiler, and it is the whole of what forall is for, so read the paragraph above as describing the intent rather than what today’s compiler does. Writing the type is accepted:

fn takes(f: forall<A>. A -> A) -> Int { 0 }

and so is passing a polymorphic function to it — takes(fn x => x) compiles. Calling f inside the body does not:

fn apply(f: forall<A>. A -> A) -> Int { let r: Int = f(1); r }

error: the type of this expression was never worked out, and nothing else was
reported — so either it needs an annotation, or this is a gap in the compiler
worth reporting

The annotation the message suggests does not help: let r: Int is already there, and instantiating by hand — let g: Int -> Int = f; — fails the same way at the assignment. Nothing in std uses forall, which is why this has not bitten anybody here.

Until it is fixed, a polymorphic operation that has to be used is a named generic function or a trait method rather than a stored function value.

Variance annotations

Covariant parameter:

pub type Source<+A>;

Contravariant parameter:

pub type Sink<-A>;

Invariant parameter:

pub type Cell<A>;

General forms:

+A
-A
A

Variance is written on the parameter declaration itself. Reach for it when designing a reusable abstraction whose subtype relationship depends on the parameter; an ordinary data type normally leaves it unmarked.

Generic implementations

impl<A: Show> Show for Box<A> {
  fn show(self) -> String {
    Show::show(self.value)
  }
}

Type parameters immediately after impl are in scope for the implemented trait, target type, associated types, and methods in that block.

Generic effects and traits

Effects and traits may also take type parameters:

pub effect Cache<K, V> {
  get: K -> Option<V>,
}

pub trait Convert<A> {
  fn convert(self) -> A;
}

The parameter grammar is shared across functions, types, traits, effects, and implementation blocks.

See Traits for associated types and implementations and Types for function types, rows, and forall in context.