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.

The v1 boundary: an impl's subject can only be a non-generic named type or Int/Float/Bool/String (there are no conditional impls, and List[T] cannot be a subject); and a call under a trait constraint is not available in comptime. The full design is in trait.md, in Chinese.