Cats-tagless is a small library built to facilitate composing tagless final encoded algebras.

Typelevel incubator Build Status codecov Join the chat at Scala.js Latest version


Cats-tagless is available on scala 2.12, 2.13 and Scala.js. Add the following dependency in build.sbt

// latest version indicated in the badge above
libraryDependencies += "org.typelevel" %% "cats-tagless-macros" % latestVersion
// For Scala 2.13, enable macro annotations
scalacOptions += "-Ymacro-annotations"

// For Scala 2.12, scalamacros paradise is needed as well.
addCompilerPlugin("org.scalamacros" % "paradise" % "2.1.0" cross CrossVersion.full)

Auto-transforming interpreters

Say we have a typical tagless encoded algebra ExpressionAlg[F[_]]

import cats.tagless._

trait ExpressionAlg[F[_]] {
  def num(i: String): F[Float]
  def divide(dividend: Float, divisor: Float): F[Float]

With an interpreter implemented using Try

import util.Try

implicit object tryExpression extends ExpressionAlg[Try] {
  def num(i: String) = Try(i.toFloat)
  def divide(dividend: Float, divisor: Float) = Try(dividend / divisor)

Similar to simulacrum, @finalAlg adds an apply method in the companion object so that you can do implicit calling.

// res0: ExpressionAlg[Try] = repl.MdocSession$App$tryExpression$@73c7276f

Cats-tagless provides a FunctorK type class to map over algebras using catsFunctionK. More specifically With an instance of FunctorK[ExpressionAlg], you can transform an ExpressionAlg[F] to a ExpressionAlg[G] using a FunctionK[F, G], a.k.a. F ~> G.

The @autoFunctorK annotation adds the following line (among some other code) in the companion object.

object ExpressionAlg {
  implicit def functorKForExpressionAlg: FunctorK[ExpressionAlg] =

This functorKForExpressionAlg is a FunctorK instance for ExpressionAlg generated using cats.tagless.Derive.functorK. Note that the usage of @autoFunctorK, like all other @autoXXXX annotations provided by cats-tagless, is optional, you can manually add this instance yourself.

With this implicit instance in scope, you can call the syntax .mapK method to perform the transformation.

import cats.tagless.implicits._
import cats.implicits._
import cats._
implicit val fk : Try ~> Option = λ[Try ~> Option](_.toOption)
// fk: Try ~> Option = repl.MdocSession$App$$anon$14@7bfa9414

// res1: ExpressionAlg[Option] = repl.MdocSession$App$ExpressionAlg$$anon$1$$anon$2@66a373e1

Note that the Try ~> Option is implemented using kind projector’s polymorphic lambda syntax. @autoFunctorK also add an auto derivation, so that if you have an implicit ExpressionAlg[F] and an implicit F ~> G, you automatically have a ExpressionAlg[G].

Obviously FunctorK instance is only possible when the effect type F[_] appears only in the covariant position (i.e. the return types). For algebras with effect type also appearing in the contravariant position (i.e. argument types), Cats-tagless provides a InvariantK type class and an autoInvariantK annotation to automatically generate instances.

import ExpressionAlg.autoDerive._
// res2: ExpressionAlg[Option] = repl.MdocSession$App$ExpressionAlg$$anon$1$$anon$2@5f19a102

This auto derivation can be turned off using an annotation argument: @autoFunctorK(autoDerivation = false).

Make stack safe with Free

Another quick win with a FunctorK instance is to lift your algebra interpreters to use Free to achieve stack safety.

For example, say you have an interpreter using Try

@finalAlg @autoFunctorK
trait Increment[F[_]] {
  def plusOne(i: Int): F[Int]

implicit object incTry extends Increment[Try] {
  def plusOne(i: Int) = Try(i + 1)

def program[F[_]: Monad: Increment](i: Int): F[Int] = for {
  j <- Increment[F].plusOne(i)
  z <- if (j < 10000) program[F](j) else Monad[F].pure(j)
} yield z

Obviously, this program is not stack safe.


Now lets use auto derivation to lift the interpreter with Try into an interpreter with Free

import cats.arrow.FunctionK
import Increment.autoDerive._

implicit def toFree[F[_]]: F ~> Free[F, *] = λ[F ~> Free[F, *]](t => Free.liftF(t))
program[Free[Try, *]](0).foldMap(
// res4: Try[Int] = Success(10000)

Again the magic here is that Cats-tagless auto derive an Increment[Free[Try, *]] when there is an implicit Try ~> Free[Try, *] and a Increment[Try] in scope. This auto derivation can be turned off using an annotation argument: @autoFunctorK(autoDerivation = false).

Vertical composition

Say you have another algebra that could use the ExpressionAlg.

trait StringCalculatorAlg[F[_]] {
  def calc(i: String): F[Float]

When writing interpreter for this one, we can call for an interpreter for ExpressionAlg.

class StringCalculatorOption(implicit exp: ExpressionAlg[Option]) extends StringCalculatorAlg[Option] {
  def calc(i: String): Option[Float] = {
    val numbers = i.split("/")
    for {
      s1 <- numbers.headOption
      f1 <- exp.num(s1)
      s2 <- numbers.lift(1)
      f2 <- exp.num(s2)
      r <- exp.divide(f1, f2)
    } yield r

Note that the ExpressionAlg interpreter needed here is a ExpressionAlg[Option], while we only defined a ExpressionAlg[Try]. However since we have a fk: Try ~> Option in scope, we can automatically have ExpressionAlg[Option] in scope through autoDerive. We can just write

new StringCalculatorOption
// res5: StringCalculatorOption = repl.MdocSession$App$StringCalculatorOption@3ada7554

Horizontal composition

You can use the SemigroupalK type class to create a new interpreter that runs two interpreters simultaneously and return the result as a cats.Tuple2K. The @autoSemigroupalK attribute add an instance of SemigroupalK to the companion object. Example:

val prod = ExpressionAlg[Option].productK(ExpressionAlg[Try])
// prod: ExpressionAlg[data.Tuple2K[Option, Try, γ$0$]] = repl.MdocSession$App$ExpressionAlg$$anon$5$$anon$6@3894f726
// res6: data.Tuple2K[Option, Try, Float] = Tuple2K(Some(2.0F), Success(2.0F))

If you want to combine more than 2 interpreters, the @autoProductNK attribute add a series of product{n}K (n = 3..9) methods to the companion object.

For example.

val listInterpreter = ExpressionAlg[Option].mapK(λ[Option ~> List](_.toList))
val vectorInterpreter = listInterpreter.mapK(λ[List ~> Vector](_.toVector))
val prod4 = ExpressionAlg.product4K(ExpressionAlg[Try], ExpressionAlg[Option], listInterpreter, vectorInterpreter)
// prod4: ExpressionAlg[Tuple4[Try[T], Option[T], List[T], Vector[T]]] = repl.MdocSession$App$ExpressionAlg$$anon$8@154fa4cf

// res7: (Try[Float], Option[Float], List[Float], Vector[Float]) = (
//   Success(3.0F),
//   Some(3.0F),
//   List(3.0F),
//   Vector(3.0F)
// )

// res8: (Try[Float], Option[Float], List[Float], Vector[Float]) = (
//   Failure(java.lang.NumberFormatException: For input string: "invalid"),
//   None,
//   List(),
//   Vector()
// )

Unlike productK living in the SemigroupalK type class, currently we don’t have a type class for these product{n}K operations yet.

@autoFunctor and @autoInvariant

Cats-tagless also provides three derivations that can generate cats.Functor, cats.FlatMap and cats.Invariant instance for your trait.


@finalAlg @autoFunctor
trait SimpleAlg[T] {
  def foo(a: String): T
  def bar(d: Double): Double

implicit object SimpleAlgInt extends SimpleAlg[Int] {
  def foo(a: String): Int = a.length
  def bar(d: Double): Double = 2 * d
SimpleAlg[Int].map(_ + 1).foo("blah")
// res9: Int = 5

Methods which return not the effect type are unaffected by the map function.

SimpleAlg[Int].map(_ + 1).bar(2)
// res10: Double = 4.0


trait StringAlg[T] {
  def foo(a: String): T

object LengthAlg extends StringAlg[Int] {
  def foo(a: String): Int = a.length

object HeadAlg extends StringAlg[Char] {
  def foo(a: String): Char = a.headOption.getOrElse(' ')

val hintAlg = for {
  length <- LengthAlg
  head <- HeadAlg
} yield head.toString ++ "*" * (length - 1)"Password")
// res11: String = "P*******"


@finalAlg @autoInvariant
trait SimpleInvAlg[T] {
  def foo(a: T): T

implicit object SimpleInvAlgString extends SimpleInvAlg[String] {
  def foo(a: String): String = a.reverse
// res12: Int = 21


@finalAlg @autoContravariant
trait SimpleContraAlg[T] {
  def foo(a: T): String

implicit object SimpleContraAlgString extends SimpleContraAlg[String] {
  def foo(a: String): String = a.reverse
// res13: String = "21"

Note that if there are multiple type parameters on the trait, @autoFunctor, @autoInvariant, @autoContravariant will treat the last one as the target T.