Traits

Traits are one of the ways to support a high level of genericity in functional programming. Flix's traits largely follow the style of type classes in Haskell, with some additional principles.

Essentials

The function isSingleton naively determines whether a list has exactly one element. However, it only works with lists. Although checking the length of a collection like this is possible for all standard collections, we have to implement a separate isSingleton function for each of them.

def isSingleton(l: List[a]): Bool =
    List.length(l) == 1

We can generalize this behavior by using a trait constraint. Rather than requiring the argument to be a list, we use a type variable a and constrain it with to the trait Length, which means that the function Length.length can be applied to the argument.

def isSingleton(l: a): Bool with Length[a] =
    Length.length(l) == 1

The trait declaration Length specifies what can be done with its members. In this case, there is only one function: Length.length, which takes the member type as an argument and returns an integer. The law nonnegative is also defined as part of the trait. Laws will be further explored below.

pub trait Length[a] {
    pub def length(x: a): Int32

    law nonnegative: forall(x: a) . Length.length(x) >= 0
}

If we try to use the new isSingleton function, we will see that it fails to compile:

isSingleton(1 :: 2 :: Nil)

While we know that a list has a length, we haven't told this to the compiler. To do this, we introduce an instance of the trait for the generic type List[a].

instance Length[List[a]] {
    pub def length(x: List[a]): Int32 = List.length(x)
}

This instance simply states that in order to get the length of the list, we just use the List.length function from the standard library. With this instance around, the call to the isSingleton function will compile. However, you may have noticed that our implementation is inefficient. While comparing the length to 1 is a correct solution generally, for lists specifically the solution has a greater runtime complexity than necessary. In order to preserve the general solution while allowing for optimizations where needed, we can use a default implementation in the trait and an override implementation in the instance.

pub trait Length[a] {

    pub def length(x: a): Int32

    pub def isSingleton(x: a): Bool = length(x) == 1

    law nonnegative: forall(x: a) . Length.length(x) >= 0

    law singletonMeansOne: forall(x: a) . Length.length(x) == 1 <==> Length.isSingleton(x)
}

instance Length[List[a]] {
    pub def length(x: List[a]): Int32 = List.length(x)
    override pub def isSingleton(x: List[a]): Bool = match x {
        case _ :: Nil => true
        case _ => false
    }
}

We have added the isSingleton function to the Length trait, with a default implementation that works in general. (We also added a new law singletonMeansOne; see section Laws.) We have added an efficient override implementation of isSingleton to the Length instance for List[a]. The advantage of the default implementation is that if there's no special behavior needed for a type, the default is assumed. The function does not have to be implemented.

instance Length[String] {
    pub def length(x: String): Int32 = String.length(x)
}

The instance Length[String] simply uses the default implementation of the isSingleton function.

Laws

In addition to the functions forming part of their contract, traits have laws that govern how the functions may be implemented.

pub trait Length[a] {
    pub def length(x: a): Int32

    law nonnegative: forall(x: a) . Length.length(x) >= 0
}

The nonnegative law asserts that the length of something can never be negative.

Planned Feature

We plan to implement a quickcheck framework to verify that these laws hold. For now, however, they only serve as a form of documentation.

Type Constraints

We've seen type constraints on on function definitions, but constraints can appear on on instances and traits themselves as well.

pub trait TreeSize[a] {
    /// Returns the number of nodes in the object graph of this object
    pub def size(x: a): Int32

    law positive: forall(x: a) . size(x) > 0
}

instance TreeSize[Int32] {
    pub def size(x: Int32): Int32 = 1
}

instance TreeSize[List[a]] with TreeSize[a] {
    pub def size(x: List[a]): Int32 = {
        // one node for each cons cell, one for the nil, and nodes for each node's value
        List.Length(x) + 1 + List.foldLeft((acc, y) -> acc + TreeSize.size(y), 0, x)
    }
}

Sealed Traits

In general, a user can add an instance of a trait for any type they define. In some cases, however, it is useful to restrict membership in a trait to a finite list of types, defined by the author of the trait. This is the purpose of a sealed trait, for which instances outside the trait's namespace are not permitted.

sealed trait Primitive[a]

instance Primitive[Bool]
instance Primitive[Int32]
instance Primitive[Float64]
// ... and so on