- Define the algebra: what we want to be able to do, but not how we will do it.
- Use the algebra to construct a program.
- Create an interpreter of the algebra.
- Run the program using the interpreter.
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!")
// )
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")
// )
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 |