oumsofiane1 · October 20, 2018 00:04
diff --git a/gistfile1.txt b/gistfile1.txt
 # 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:
 ```scala
 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:
 ```scala
 // 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:
 ```scala
 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:
 ```scala
 taglessProgram[Try]("12345")
 // res0: Try[List[String]] = Success(
 //   List("whee!", "whee!", "whee!", "whee!", "whee!")
 // )
 ```
 ## Free encoding
 Define the algebra:
 ```scala
 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:
 ```scala
 def freeProgram(s: String): DoSomethingFreeAlgebra[List[String]] =
  for {
    i <- DoSomethingFreeAlgebra.doSomething(s)
    ss <- DoSomethingFreeAlgebra.doSomethingElse(i)
  } yield ss
 ```
 Create an interpreter of the algebra:
 ```scala
 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:
 ```scala
 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]` <br/>, parameterized by _effect type_ `F[_]` | an algebraic data type `Alg[A]` <br/>, 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
	# 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:
	```scala
	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:
	```scala
	// 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:
	```scala
	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:
	```scala
	taglessProgram[Try]("12345")
	// res0: Try[List[String]] = Success(
	// List("whee!", "whee!", "whee!", "whee!", "whee!")
	// )
	```
	## Free encoding
	Define the algebra:
	```scala
	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:
	```scala
	def freeProgram(s: String): DoSomethingFreeAlgebra[List[String]] =
	for {
	i <- DoSomethingFreeAlgebra.doSomething(s)
	ss <- DoSomethingFreeAlgebra.doSomethingElse(i)
	} yield ss
	```
	Create an interpreter of the algebra:
	```scala
	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:
	```scala
	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]` <br/>, parameterized by _effect type_ `F[_]` \| an algebraic data type `Alg[A]` <br/>, 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