16. trait: constrained generics and operator overloading

Up to here a generic function has known nothing about T — it cannot compare it, print it or call a method on it. A trait attaches a capability constraint to a type parameter. Declare a trait, write an impl for a concrete type, then constrain the generic with [T: Trait]:

trait Area[T] {
  fn area(s: T) -> Float
  fn bigger_than(s: T, limit: Float) -> Bool = area(s) > limit
}

type Rect = { w: Float, h: Float }

impl Area[Rect] {
  fn area(s: Rect) -> Float = s.w * s.h
}

fn total_area[T: Area](xs: List[T]) -> Float =
  fold(xs, 0.0, (acc, x) => acc + area(x))

pub fn main() -> Unit !io = {
  let rooms = [Rect { w: 3.0, h: 4.0 }, Rect { w: 2.0, h: 2.0 }]
  println(to_string(total_area(rooms)))
  # a trait method is an ordinary function name, so a UFCS dot call works too
  println(to_string(rooms[0].bigger_than(10.0)))
}

16.0
true

The rules are few: a trait has exactly one type parameter; each "trait × type" pair admits exactly one impl in the whole program; and an impl has to be written in the module of either the trait or the subject type (the orphan rule). A method with a default body (bigger_than above) may be left out of an impl, and writing it is an override.

Sorting: Ord and the comparison operators#

The built-in trait Ord[T] — one method, cmp(a: T, b: T) -> Int, negative/zero/ positive for less/equal/greater — is what bridges < <= > >=. Int/Float/String are ordered from the start; give a type of your own an Ord impl (or just derive Ord) and it can use the comparison operators, be passed where [T: Ord] is asked for, and be fed to the sorting functions:

type Card = { rank: Int, name: String } derive Show, Ord

fn max2[T: Ord](a: T, b: T) -> T = if a < b { b } else { a }

pub fn main() -> Unit !io = {
  let hand = [Card { rank: 3, name: "queen" }, Card { rank: 1, name: "pawn" }]
  # derive Ord compares field by field in declaration order (a sum type compares constructors first)
  println(to_string(hand[1] < hand[0]))
  println(max2("pear", "apple"))
  println(to_string(sort([3, 1, 2])))
  println(to_string(map(sort(hand), c => c.name)))
  println(to_string(max_by(hand, c => c.rank)))
}

true
pear
[1, 2, 3]
["pawn", "queen"]
Some(Card { rank: 3, name: "queen" })

The list functions that go with it are stable sorts that keep the first of a tie: sort/max/min want Ord on the element, sort_by(xs, cmp) takes a comparison function of your own, and max_by/min_by(xs, key) take the extreme by a key (whose type needs Ord).

A trait method, or any function with a bound, can be passed around as a bare function value. What it needs is an expected function type, because that is what says which type the bound is discharged at; the wrapper is then written for you, dictionary and all:

fn shout[T: Show](xs: List[T]) -> List[String] = map(xs, to_string)

pub fn main() -> Unit !io = {
  println(join(shout([1, 2, 3]), " "))
  # the bound here is `shout`'s own, so the wrapper closes over the dictionary
  # `shout` was handed, which is what `x => to_string(x)` would have done
  println(join(shout(["a", "b"]), " "))
}

1 2 3
"a" "b"

Without one, as in let f = to_string, there is nothing to discharge the bound at and the compiler says so; write the type, or write the lambda with an annotated parameter.

One list, many types: a record of functions#

A List[T] holds one T. When you want a list of different types that all support the same operation, Dawn has no dyn Trait to reach for. Capture the operation in a record of functions, hide the record behind an opaque type, and give that type an impl of its own. The bound is discharged where the value is packed, which is the last place the concrete type is still known:

type ShownRepr = { render: fn() -> String }

pub opaque type Shown = ShownRepr

pub fn shown[T: Show](x: T) -> Shown = {
  let r: ShownRepr = ShownRepr { render: () => show(x) }
  r
}

impl Show[Shown] {
  fn show(s: Shown) -> String = {
    let r: ShownRepr = s
    r.render()
  }
}

pub fn main() -> Unit !io = {
  let xs: List[Shown] = [shown(1), shown("two"), shown(true)]
  for x in xs {
    println("${x}")
  }
}

1
"two"
true

The second line keeps its quotes. That is what Show[String] renders, here and everywhere else, and not a slip in the example.

The trick is complete for a trait that takes its subject in one position: Show, Hash, anything shaped fn(T) -> .... It does not reach Eq or Ord, whose eq(a: T, b: T) and cmp(a: T, b: T) need two values of the same type, and packing is exactly what throws that fact away. So a heterogeneous List is available and a heterogeneous Map key is not. Why the line falls there, and why Dawn does not add trait objects, is in trait.md §10, in Chinese.

An impl's subject may be generic: impl[T: Eq] Eq[List[T]] is a conditional impl, and derive on a generic type writes one (type Box[T] = { v: T } derive Ord gives impl[T: Ord] Ord[Box[T]]). The v1 boundary: the subject's arguments must be the impl's own, distinct type parameters (impl Eq[List[Int]] is rejected); and a call under a trait constraint is not available in comptime. The full design is in trait.md, in Chinese.

Associated types, and the traits behind [] and for#

A trait can declare a type of its own that each impl fills in: type Item in the trait, type Item = String in the impl. A signature reaches it through the type parameter, as C.Item, so a generic function can talk about "whatever this container holds" without being told what that is:

trait Store[C] {
  type Key
  type Item
  fn fetch(c: C, k: C.Key) -> Option[C.Item]
}

type Shelf = { names: List[String] }

impl Store[Shelf] {
  type Key = Int
  type Item = String
  fn fetch(c: Shelf, k: Int) -> Option[String] = get(c.names, k)
}

# a generic consumer: whatever the store's key and item are, it uses them as they are
fn fetch_or[C: Store](c: C, k: C.Key, fallback: C.Item) -> C.Item =
  match fetch(c, k) {
    Some(x) -> x
    None -> fallback
  }

pub fn main() -> Unit !io = {
  let s = Shelf { names: ["tea", "rice"] }
  println(fetch_or(s, 1, "nothing"))
  println(fetch_or(s, 5, "nothing"))
}

rice
nothing

fetch_or is checked once, against the trait, and at each call C.Item becomes the impl's binding, so fetch_or(s, 1, "nothing") takes and returns a String. An impl binds each associated type exactly once; leaving one out, or binding a name the trait does not declare, is an error.

Two of the built-in traits are written this way, and they are the ones the language's own syntax goes through. Index[C] has type Idx, type Item and one method, index, and it is what c[i] calls: List (indexed by Int) and Map (by its key) come with impls, and one impl gives a type of your own []. Iter[C] has type Cur, type Item and four cursor methods, and it is what for x in c walks:

type Grid = { w: Int, cells: List[Int] }

impl Index[Grid] {
  type Idx = (Int, Int)
  type Item = Int
  fn index(g: Grid, p: (Int, Int)) -> Int = {
    let (x, y) = p
    g.cells[y * g.w + x]
  }
}

type Countdown = { from: Int }

impl Iter[Countdown] {
  type Cur = Int
  type Item = Int
  fn iter_start(it: Countdown) -> Int = it.from
  fn iter_done(it: Countdown, c: Int) -> Bool = c == 0
  fn iter_next(it: Countdown, c: Int) -> Int = c - 1
  fn iter_get(it: Countdown, c: Int) -> Int = c
}

pub fn main() -> Unit !io = {
  let g = Grid { w: 3, cells: [1, 2, 3, 4, 5, 6] }
  println("${g[(2, 1)]}")
  let launch = Countdown { from: 3 }
  for n in launch {
    print("${n} ")
  }
  println("liftoff")
}

6
3 2 1 liftoff

Both traits are in the prelude, so neither impl needs a use. [] is read-only (there is no c[i] = v), and a type has exactly one index type. index itself cannot be called by name, because [] is its spelling; the four Iter methods can.

See also: spec.en.md §3.5, §4.8