Tagless unions in scala 2.12

4 min readMay 17, 2019

So you’ve found yourself again in this situation.
You have 2+ error ADTs like this

sealed trait PasswordError

object PasswordError{
  case class TooShort(required: Int) extends PasswordError
  case class ToesNotContain(chars: String) extends PasswordError
}

And this

sealed trait LoginError

object LoginError{
  case class TooLong(maxLength: Int) extends LoginError
  case object BadFormat extends LoginError
}

Next, you use some monadic type, using checked errors like
Either or ZIO, and have some of the code like having different checked errors

def validateLogin(login: String): ZIO[HasLoginConfig, LoginError, Unit]def validatePassword(pass: String): ZIO[HasPasswordConfig, PasswordError, Unit]

And you’d like to use both of them in the single expression, so that result type can express the possibility of either error

def validateUser(user: User) = 
  validateLogin(user.login) *> validatePassword(user.pass)

Good news: your error type parameter has “covariant” tag so you can expect something like

ZIO[
  HasLoginConfig & HasPasswordConfig, 
  LoginError | PasswordError
, Unit]

Bad news: scala 2 still has not any type union operation, yet it has the with operator: not-always-commutative type intersection

If you aren’t familiar with tagless final approach yet it’s about time. There is plenty of videos like that one, just google it

So start from redefining your error ADT’s as single parameter traits like

trait LoginErr[+A] {
  def tooLong(maxLength: Int): A
  def badFormat: A
}trait PasswordErr[+A] {
  def tooShort(required: Int): A
  def doesNotContain(chars: String): A
}

Starting from here, LoginErr[A] is equivalent to LoginError => A it’s just little bit more effective.

If you had pattern matching like

{
  case TooLong(x) => a
  case BadFormat => b
}

you may just replace it with

new LoginErr[X] {
  def tooLong(x: Int) = a
  def badFormat = b
}

And we have exhaustiveness check for free

But what should we match? We might need some “initial” form of our algebra, let’s introduce the universal initializer

trait Capture[-F[_]] {
  def continue[A](k: F[A]): A
}

Here F is the placeholder for your algebra, e.g. LoginErr or PasswordErr

To apply the “pattern matching” you need just pass your LoginErr[X] to the continue method and get back your X result

Why have we marked our -F[_] as contravariant? This is the main part

So our capture is just a natural (hopefully) transformation F ~> Id with covariance on the argument functor

Recalling that we are going to use some “algebras” as F it’s just a
[A] (ADT => A) => A where [A] f[A] is just a fancy syntax for higher-ranked type, forall a. f a if you prefer

According to Yoneda lemma[A] (ADT => A) => A is moral equivalent to ADT, you can verify just applying Yoneda to Scala wannabe-category and Id endofunctor, that means that Capture[LoginErr] is same as LoginError from our first attempt

Next, we might play a little bit with variances, if C[+A] is covariant you’ll have

C[A] & C[B] = C[A & B]
C[A] | C[B] = C[A | B]

Сonversely if C[-A] is contravariant you’ll have

C[A] & C[B] = C[A | B]
C[A] | C[B] = C[A & B]

Scala might not have | and & operations on type level, but those rules are effective when scalac is searching for least upper and greatest lower bounds during the type inference.

Recalling that functions -A => +B are covariant on the result and contravariant on the parameter we may conclude that

PasswordErr[A] & LoginErr[A] ~
(PasswordError => A) & (LoginError => A) =
(PasswordError | LoginError) => A

So PasswordErr[A] with LoginErr[A] is a special type that is effectively algebra corresponding to some union ADT PasswordError | LoginError

And that’s great because when compiler search for the least upper bound of

Capture[PasswordErr] and Capture[LoginError]

it should find

Capture[[A] PasswordErr[A] with LoginErr[A]]

due to Capture contravariance which is moral equivalent to union PasswordError | LoginError. And to “pattern match” it you need to implement merged PasswordErr with LoginErr , that will require you to implement all four methods, that is pattern match all four possible constructors

Now it’s time for some boilerplate.

For the real use, we’ll need easy Capture construction, without hesitation, we use Alex Konovalov’s trick for higher-ranked lambdas

object Capture {
  type Arbitrary

  def apply[F[_]] = new Apply[F]

  class Apply[F[_]] {
    def apply(f: F[Arbitrary] => Arbitrary): Capture[F] = 
    new Capture[F] {
      def continue[A](k: F[A]): A = 
         f(k.asInstanceOf[F[Arbitrary]]).asInstanceOf[A]
    }
  }
}

Now we can implement the initial algebra, that is — implementation of our algebra trait for the initial Capture type

object LoginErr extends LoginErr[Capture[LoginErr]] {
  def tooLong(maxLength: Int) =  
      Capture[LoginErr](_.tooLong(maxLength))
  val badFormat               = 
      Capture[LoginErr](_.badFormat)
}

this methods could be used as constructor, we can simplify types defining

type Constructors[F[_]] = F[Capture[F]]

The full code can be found in this repo https://github.com/Odomontois/zio-tagless-err

Special thanks to https://t.me/scala_ponv community for the forcing to write my debut blog post

Any remarks, corrections, including English grammar are appreciated

Tagless unions in scala 2.12

Written by Oleg Nizhnik