Associated Types

An associated type is a type member of a trait that is specified by each trait instance. Associated types are often considered a more natural alternative to multi-parameter type classes.

We illustrate associated types with an example.

We can define a trait for types that can be added:

trait Addable[t] {
    pub def add(x: t, y: t): t
}

We can implement multiple instances of the Addable trait for types such as floating-point numbers, integers, and strings. For example, here is the instance for Int32:

instance Addable[Int32] {
    pub def add(x: Int32, y: Int32): Int32 = x + y
}

and here is one for String:

instance Addable[String] {
    pub def add(x: String, y: String): String = "${x}${y}"
}

But what if we wanted to add an element to a set?

Intuitively, we would like to write:

instance Addable[Set[a]] with Order[a] {
    pub def add(s: Set[a], x: a): Set[a] = Set.insert(x, s)
}

But the signature of add does not match the signature declared in Addable.

We can overcome this problem and increase the flexibility of Addable with an associated type:

trait Addable[t] {
    type Rhs
    pub def add(x: t, y: Addable.Rhs[t]): t
}

The Addable trait now has an associated type called Rhs. We refer to it as Addable.Rhs[t] as seen in the signature of add. Whenever we declare an instance of Addable, we must specify the associated type.

We can still implement instances for integers and strings, as before. For example:

instance Addable[Int32] {
    type Rhs = Int32
    pub def add(x: Int32, y: Int32): Int32 = x + y
}

But we can also implement an instance that allows adding an element to a set:

instance Addable[Set[a]] with Order[a] {
    type Rhs = a
    pub def add(s: Set[a], x: a): Set[a] = Set.insert(x, s)
}

The important point is that each trait instance specifies the associated type.

We might wonder if we can specify two instances for Set[a]: (a) one for adding an element to a set, as above, and (b) one for adding two sets:

instance Addable[Set[a]] with Order[a] {
    type Rhs = Set[a]
    pub def add(x: Set[a], y: Set[a]): Set[a] = Set.union(x, y)

}

But while each instance is valid on its own, we cannot have both:

❌ -- Instance Error -------------------------------------------------- 

>> Overlapping instances for 'Addable'.

...

If we had such overlapping instances, an expression like Addable.add(Set#{}, Set#{}) would become ambiguous: Are we adding two sets? Or are we adding the empty set to a set?

Example: A `ForEach` Trait

We can use associated types to define a trait for collections that have a forEach function:

trait ForEach[t] {
    type Elm
    pub def forEach(f: ForEach.Elm[t] -> Unit \ ef, x: t): Unit \ ef
}

Here t is the type of the collection and the associated type Elm is the type of its elements. We can implement several instances for ForEach. For example, we can implement an instance for List[a]:

instance ForEach[List[a]] {
    type Elm = a
    pub def forEach(f: a -> Unit \ ef, x: List[a]): Unit \ ef = List.forEach(f, x)
}

We can also implement an instance for Map[k, v]:

instance ForEach[Map[k, v]] {
    type Elm = (k, v)
    pub def forEach(f: ((k, v)) -> Unit \ ef, x: Map[k, v]): Unit \ ef = 
        Map.forEach(k -> v -> f((k, v)), x)
}

What is interesting and useful is that we can define the element type to be key-value pairs. We need extra parentheses around the argument to f because we want it to take a pair.

We can implement an instance for String where we can iterate through each individual character:

instance ForEach[String] {
    type Elm = Char
    pub def forEach(f: Char -> Unit \ ef, x: String): Unit \ ef = 
        x |> String.toList |> List.forEach(f)
}

Example: A `Collection` Trait

As another example, we can define a trait for collections:

trait Collection[t] {
    type Elm
    pub def empty(): t
    pub def insert(x: Collection.Elm[t], c: t): t
    pub def toList(c: t): List[Collection.Elm[t]]
}

Here t is the type of the collection and Elm is the type of its elements. Every collection must support three operations: empty, insert, and toList.

We can implement an instance of Collection for Vector[a]:

instance Collection[Vector[a]] {
    type Elm = a
    pub def empty(): Vector[a] = Vector.empty()
    pub def insert(x: a, c: Vector[a]): Vector[a] = Vector.append(c, Vector#{x})
    pub def toList(c: Vector[a]): List[a] = Vector.toList(c)
}

And we can implement an instance of Collection for Set[a]:

instance Collection[Set[a]] with Order[a] {
    type Elm = a
    pub def empty(): Set[a] = Set.empty()
    pub def insert(x: a, c: Set[a]): Set[a] = Set.insert(x, c)
    pub def toList(c: Set[a]): List[a] = Set.toList(c)
}

Equality Constraints

We sometimes want to write polymorphic functions where we restrict an associated type.

For example, returning to the example of the Collection trait, we can write a function where we require that the element type is an Int32. This allows us to write a sum function:

def sum(c: t): Int32 with Collection[t] where Collection.Elm[t] ~ Int32 = 
    Collection.toList(c) |> List.sum

Here the where clause contains a list of type equality constraints. Specifically, the equality constraint Collection.Elm[t] ~ Int32 assert that sum can be used with any type t for which there is an instance of Collection as long as the element type of that instance is equal to Int32. This restriction ensures that the elements of the collection are integers and allows us to call List.sum.

Default Types

We can define a default type for an associated type.

Returning to Addable, we can define the associated type Rhs with t as its default:

trait Addable[t] {
    type Rhs = t  // Associated type with default type.
    pub def add(x: t, y: Addable.Rhs[t]): t
}

Here we specify that if Rhs is not defined by an instance implementation then it defaults to t. The upshot is that we can define an instance for Int32:

instance Addable[Int32] {
    pub def add(x: Int32, y: Int32): Int32 = x + y
}

without having to explicit define type Rhs = Int32.

Programming Flix