Timothy McCarthy

### Categories

In my previous post, I discussed using Invariant to add behaviour to value classes. Unfortunately, Invariant is not powerful enough to provide instances for higher-kinded type classes like Functor or Traverse. In this post, I’ll introduce InvariantK, a type class I’ve written to solve this limitation.

## Value classes with a type parameter

As I discussed previously, wrapping common types in dedicated classes (“value classes”) comes with a number of advantages. Value classes have a semantic meaning that more common types do not, and we can use this technique to get help from the compiler to avoid bugs.

Sometimes, these principles apply to generic types in the same way as they apply to normal types.

Consider this type called Uncertain.

sealed trait Uncertain[+A]

case object Unknown             extends Uncertain[Nothing]
final case class Known[A](a: A) extends Uncertain[A]


Uncertain represents some value that we may know or not know. It is obviously very similar to Option. Known maps directly to Some, and Unknown maps to None. But Uncertain has a different semantic meaning, which is now clear everywhere we use it.

Compare:

final case class Person(
name: String,
age: Option[Int],
)


versus

final case class Person(
name: String,
age: Uncertain[Int],
)


The meaning of the age field in the first case is ambiguous and a little silly. Every person has an age, so how could it ever be None? But if we use Uncertain, it becomes clear what we’re attempting to model. We are handling the case where we don’t know the person’s age.

## Using Invariant to define instances for Uncertain

In my last post I described how we can use the imap function provided by Invariant to easily define type class instances based on an underlying type. Given Uncertain is just like Option, can we do something similar here?

First of all, we’ll need two functions for converting between Option[A] and Uncertain[A]:

def optionToUncertain[A](option: Option[A]): Uncertain[A] = option match {
case Some(a) => Known(a)
case None    => Unknown
}

def uncertainFromOption[A](uncertain: Uncertain[A]): Option[A] = uncertain match {
case Known(a) => Some(a)
case Unknown  => None
}


For simple cases, using imap works well. For example, we can define an Eq instance easily:

import cats._
import cats.syntax.all._

implicit def eqForUncertain[A: Eq]: Eq[Uncertain[A]] = Eq[Option[A]].imap(optionToUncertain)(uncertainFromOption)

Eq[Uncertain[Int]].eqv(Known(1), Known(1)) // true
Eq[Uncertain[Int]].eqv(Known(1), Unknown)  // false


But what about the more complex operations on Option like .map? This comes from the Functor type class. If we had a Functor we could do useful things like describing whether a Person is over 18:

implicit val functorForUncertain: Functor[Uncertain] = ???

val p1 = Person(name = "👶", age = Known(3))
val p2 = Person(name = "💆", age = Unknown)

def isAdult(age: Int): Boolean = age >= 18



Unfortunately, Invariant is not powerful enough to define a Functor for Uncertain. This is because Functor is a higher-kinded type class. Put another way, whereas type classes like Eq[A] and Semigroup[A] accept a simple type parameter, Functor[F[_]] only applies to types that themselves have a type parameter. We might say that the F[_] in Functor[F[_]] has to “have a type hole” or “be a type constructor”.

We need to find another solution.

## The InvariantK type class

The solution is to create a type class similar to Invariant, but which works on higher-kinded types rather than normal types. There is a similar distinction between functions (which act on normal types) and FunctionK. Accordingly, what we need is something called InvariantK.

Consider how Invariant is defined (cf. Cats implementation):

trait Invariant[F[_]] {
def imap[A, B](fa: F[A])(f: A => B)(g: B => A): B
}


If we move each concept in this definition “up” by one “kind”, we end up with:

import cats.~>

trait InvariantK[T[_[_]]] {
def imapK[F[_], G[_]](tf: T[F])(f: F ~> G)(g: G ~> F): T[G]
}


This is pretty mind-bending. T[_[_]] is a doubly-higher-kinded type! And notice that f and g are now instances of FunctionK (using the ~> notation) to transform between the two higher-kinded types F[_] and G[_].

I’ve implemented InvariantK in my personal library of Cats utilities. It’s available here. We can use it to define a Functor for Uncertain:

import au.id.tmm.utilities.cats.classes.InvariantK
import au.id.tmm.utilities.cats.syntax.all._
import cats._
import cats.arrow.FunctionK
import cats.syntax._

val optionToUncertain: Option ~> Uncertain = new FunctionK[Option, Uncertain] {
override def apply[A](option: Option[A]): Uncertain[A] = option match {
case Some(a) => Known(a)
case None => Unknown
}
}

val uncertainToOption: Uncertain ~> Option = new FunctionK[Uncertain, Option] {
override def apply[A](uncertain: Uncertain[A]): Option[A] = uncertain match {
case Known(a) => Some(a)
case Unknown  => None
}
}

implicit val functorForUncertain: Functor[Uncertain] = Functor[Option].imapK(optionToUncertain)(uncertainToOption)

val p1 = Person(name = "👶", age = Known(3))
val p2 = Person(name = "💆", age = Unknown)

def isAdult(age: Int): Boolean = age >= 18


Once we have Option ~> Uncertain and Uncertain ~> Option, we can define a Functor for Uncertain. In fact, we can use these FunctionK instances to define a number of type class instances for Uncertain:
implicit val monadErrorForUncertain: Monad[Uncertain]  = Monad[Option].imapK(optionToUncertain)(uncertainToOption)

Check out tmmUtils. It has a bunch of utilities I’ve found useful, including InvariantK.