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.11, 2.12, and scalajs. The macro annotations are developed using scalameta, so there are a few dependencies to add in your build.sbt.

  ("org.scalameta" % "paradise" % "3.0.0-M11").cross(CrossVersion.full))

libraryDependencies += 
  "org.typelevel" %% "cats-tagless-macros" % latestVersion  //latest version indicated in the badge above

Note that org.scalameta.paradise is a fork of org.scalamacros.paradise. So if you already have the org.scalamacros.paradise dependency, you might need to replace it.

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[scala.util.Try] = tryExpression$@2ff2eb48

Cats-tagless provides a FunctorK type class to map over algebras using catsFunctionK. The @autoFunctorK annotation automatically generate an instance of FunctorK for ExpressionAlg so that you can map an ExpressionAlg[F] to a ExpressionAlg[G] using a FunctionK[F, G], a.k.a. F ~> G.

import cats.tagless.implicits._
import cats.implicits._
import cats._
implicit val fk : Try ~> Option = λ[Try ~> Option](_.toOption)
// fk: scala.util.Try ~> Option = $anon$1@1bedc2d9

// res1: ExpressionAlg[Option] = ExpressionAlg$$anon$1$$anon$5@57e21535

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._
// import ExpressionAlg.autoDerive._

// res2: ExpressionAlg[Option] = ExpressionAlg$$anon$1$$anon$5@6c44a1e

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.

//throws java.lang.StackOverflowError

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(
// res3: scala.util.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

import ExpressionAlg.autoDerive._
// import ExpressionAlg.autoDerive._

new StringCalculatorOption
// res4: StringCalculatorOption = StringCalculatorOption@207f3981

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[[γ$0$][Option,scala.util.Try,γ$0$]] = ExpressionAlg$$anon$3$$anon$7@44ff0f83

// res5:[Option,scala.util.Try,Float] = Tuple2K(Some(2.0),Success(2.0))

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[[T](scala.util.Try[T], Option[T], List[T], Vector[T])] = ExpressionAlg$$anon$9@454c3dc0

// res6: (scala.util.Try[Float], Option[Float], List[Float], Vector[Float]) = (Success(3.0),Some(3.0),List(3.0),Vector(3.0))

// res7: (scala.util.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 annotations 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")
// res8: Int = 5

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

SimpleAlg[Int].map(_ + 1).bar(2)
// res9: 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")
// res10: 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
// res11: Int = 21


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

implicit object SimpleInvAlgString extends SimpleInvAlg[String] {
  def foo(a: String): String = a.reverse
// res12: 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.