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

Typelevel incubator Build Status codecov Join the chat at https://gitter.im/typelevel/cats-tagless Scala.js Latest version

Installation

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._

@finalAlg
@autoFunctorK
@autoSemigroupalK
@autoProductNK
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.

ExpressionAlg[Try]
// 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] =
    Derive.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

tryExpression.mapK(fk)
// 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._
ExpressionAlg[Option]
// 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.

program[Try](0)

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

import cats.free.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(FunctionK.id)
// 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
prod.num("2")
// 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

prod4.num("3")
// res7: (Try[Float], Option[Float], List[Float], Vector[Float]) = (
//   Success(3.0F),
//   Some(3.0F),
//   List(3.0F),
//   Vector(3.0F)
// )

prod4.num("invalid")
// 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.

@autoFunctor

@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

@autoFlatMap

@autoFlatMap
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)
hintAlg.foo("Password")
// res11: String = "P*******"

@autoInvariant

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

implicit object SimpleInvAlgString extends SimpleInvAlg[String] {
  def foo(a: String): String = a.reverse
}
SimpleInvAlg[String].imap(_.toInt)(_.toString).foo(12)
// res12: Int = 21

@autoContravariant

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

implicit object SimpleContraAlgString extends SimpleContraAlg[String] {
  def foo(a: String): String = a.reverse
}
SimpleContraAlg[String].contramap[Int](_.toString).foo(12)
// 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.