Traits

Partial Constraints

Sometimes there is enough information for the compiler to deduce a single concrete type. Other times, there is no information at all, meaning the type must be fully polymorphic. What happens in-between these two extremes? Consider this function:

let adder = fn a b => a + b

The only constraint on a and b is that they can be added together. There are many types that can be added together, including Integer, Real, and Natural. There are many more types which cannot be added together, like tuples. We need a new type of constraint that represents "one of a few types" rather than "one of any type". This is exactly the problem that traits solve.

Trait Functions

Operators in Halcyon are defined as traits. Let's examine the definition of the Add trait, which defines the + operator:

trait Add: a =
  let [+]: a -> a -> a
end

Traits almost always have a type parameter, in this case a. This trait defines just one function [+], and gives it the type a -> a -> a. Notice that there is no definition yet, only a type. Every type that can be added will have a different definition of [+]. Traits allow us to do what other languages call "function overloading".

Let's define addition for two dimensional vectors:

type Vector = {
  x: Real,
  y: Real,
}

impl Add Vector =
  let [+] = fn a b => {
    x = a.x + b.x,
    y = a.y + b.y,
  }
end

Even though the [+] function has multiple definitions, you can treat it like a single function. The compiler will select the correct implementation for you during constraint solving.

Associated Constants

Traits can define more than just functions. For example, the Default trait defines a default value for a type.

trait Default: a =
  let default: a
end

impl Default Real =
  let default = 0.0
end

impl Default Vector =
  let default = {
    x = default,
    y = default,
  }
end

let default_real: Real = default
-- 0.0
let default_vector: Vector = default
-- { x = 0.0, y = 0.0 }

This allows you to overload constants as well as functions. The correct implementation of default is chosen based on the constraints applied to it.

Trait Constraints

Trait constraints are expressed using a where clause, which must come after for .. in ..:

let adder: for a in a -> a -> a where Add a =
  fn a b => a + b

Multiple trait constraints are separated with commas.

let add_mult: for a in a -> a -> a -> a where Add a, Multiply a =
  fn a b c => a + b * c

Polymorphic Trait Implementations

Traits can be implemented for polymorphic types. The default value for Option is None regardless of what type is in the Some variant.

impl Default for a in Option a =
  let default = None
end

let default_opt_int: Option Integer = default
-- None
let default_opt_real: Option Real = default
-- None
let default_opt: Option _ = default
-- None

Combining trait constraints with impl blocks is extremely powerful. Here is how you could implement Default for all two-element tuples where both elements also implement Default:

impl Default for a b in (a, b) where Default a, Default b =
  let default = (default, default)
end

let (a, b): (Real, Vector) = default
-- (0.0, { x = 0.0, y = 0.0 })