Type Classes

Type classes are one of the ways to support a high level of genericity in functional programming. Flix's type classes largely follow the style of those of 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 type class constraint. Rather than requiring the argument to be a list, we use a type variable a and constrain it with to the type class 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 type class 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 class. Laws will be further explored below.

pub class 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 type class 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 type class and an override implementation in the instance.

pub class 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 type class, 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, type classes have laws that govern how the functions may be implemented.

pub class 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 type classes themselves as well.

pub class 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 Classes

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

sealed class Primitive[a]

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

Programming Flix