sample.md

Algebras: Free vs. Tagless Encoding

The General Pattern

1. Define the algebra: what we want to be able to do, but not how we will do it.
2. Use the algebra to construct a program.
3. Create an interpreter of the algebra.
4. Run the program using the interpreter.

Tagless encoding

Define the algebra:

import cats._
import cats.implicits._
import scala.util.Try
trait DoSomethingAlgebra[F[_]] {
  def doSomething(s: String): F[Int]
  def doSomethingElse(i: Int): F[List[String]]
}

Use the algebra to construct a program:

// We constrain F to have a Monad, so we can compose multiple operations using a for-comprehension.
def taglessProgram[F[_] : Monad](s: String)(implicit alg: DoSomethingAlgebra[F]): F[List[String]] =
  for {
    i <- alg.doSomething(s)
    ss <- alg.doSomethingElse(i)
  } yield ss

Create an interpreter of the algebra:

implicit object tryTagless extends DoSomethingAlgebra[Try] {
  def doSomething(s: String): Try[Int] =
    Try(s.length)
  def doSomethingElse(i: Int): Try[List[String]] =
    Try(List.fill(i)("whee!"))
}

Run the program using the interpreter:

taglessProgram[Try]("12345")
// res0: Try[List[String]] = Success(
//   List("whee!", "whee!", "whee!", "whee!", "whee!")
// )

Free encoding

Define the algebra:

import cats.arrow._
import cats.free.Free
// We create an algebraic data type for our operations, parameterized by operation output type.
sealed trait DoSomethingAlgebraF[A]
object DoSomethingAlgebraF {
  case class DoSomething(s: String) extends DoSomethingAlgebraF[Int]
  case class DoSomethingElse(i: Int) extends DoSomethingAlgebraF[List[String]]
}
// We wrap our algebra in the Free monad
type DoSomethingFreeAlgebra[A] = Free[DoSomethingAlgebraF, A]
// We create factory methods, sometimes called "smart constructors", to wrap each operation in Free.
object DoSomethingFreeAlgebra {
  def doSomething(s: String): DoSomethingFreeAlgebra[Int] =
    Free.liftF(DoSomethingAlgebraF.DoSomething(s))
  def doSomethingElse(i: Int): DoSomethingFreeAlgebra[List[String]] =
    Free.liftF(DoSomethingAlgebraF.DoSomethingElse(i))
}

Use the algebra to construct a program:

def freeProgram(s: String): DoSomethingFreeAlgebra[List[String]] =
  for {
    i <- DoSomethingFreeAlgebra.doSomething(s)
    ss <- DoSomethingFreeAlgebra.doSomethingElse(i)
  } yield ss

Create an interpreter of the algebra:

def tryFree[A](freeProgram: DoSomethingAlgebraF[A]): Try[A] =
  freeProgram match {
    case DoSomethingAlgebraF.DoSomething(s) => Try(s.length)
    case DoSomethingAlgebraF.DoSomethingElse(i) => Try(List.fill(i)("whee"))
  }

Run the program using the interpreter:

freeProgram("12345").foldMap(FunctionK.lift(tryFree))
// res1: Try[List[String]] = Success(
//   List("whee", "whee", "whee", "whee", "whee")
// )

Comparison

For an algebra Alg with operations, where we interpret a program that outputs an F[A]:	Using the "tagless" encoding	Using the "free" encoding
algebras are	a trait Alg[F] , parameterized by effect type F[_]	an algebraic data type Alg[A] , parameterized by output type A
programs are encoded as	composed functions	composed data
interpreters for effect F[_] are	implementations of Alg[F]	functions of type Alg[A] => F[A]
concrete effect type F[_] is chosen	as the type parameter to the algebra	via the output type of the interpreter