vvviiimmm

case class Person(name: String, age: Int)

vvviiimmm

package fme

import cats.Id
import fme.Free.NaturalTransformation

object Example1 extends App {

  /**
    * Data structures for our operations
    */

vvviiimmm

package fme

import cats.Monad

sealed trait Free[F[_], A] {
  def flatMap[B](f: A => Free[F, B]): Free[F, B] = this match {
    case Return(a)          => f(a)
    case FlatMap(sub, cont) => FlatMap(sub, cont andThen (_ flatMap f))
  }
  def map[B](f: A => B): Free[F, B] = flatMap(a => Return(f(a)))

vvviiimmm

val initialAlgebra: Algebra[ExpressionF, Fix[ExpressionF]] = Fix[ExpressionF]

vvviiimmm

// just in case
final case class Fix[F[_]](unFix: F[Fix[F]])

//                                       vvvvvvvvvvvvvvvv
val initialAlgebra: Algebra[ExpressionF, Fix[ExpressionF]] = ???

vvviiimmm

type Algebra[F[_], A] = F[A] => A

val algebra0: Algebra[ExpressionF, Int] = {
  case ValueF(v) => v
  case AddF(e1, e2) => e1 + e2
  case MultF(e1, e2) => e1 * e2
}

val algebra1: Algebra[ExpressionF, String] = {
  case ValueF(v) => v.toString

vvviiimmm

// Non recursive data structure
sealed trait ExpressionF[A]

case class ValueF[A](v: Int) extends ExpressionF[A]
case class AddF[A](e1: A, e2: A) extends ExpressionF[A]
case class MultF[A](e1: A, e2: A) extends ExpressionF[A]

// Functor instance for it
implicit object ExpressionFunctor extends Functor[ExpressionF] {
  override def map[A, B](fa: ExpressionF[A])(f: A => B): ExpressionF[B] = fa match {

vvviiimmm

def cata[F[_], A](alg: (F[A] => A))(e: Fix[F])(implicit F: Functor[F]): A =
  alg(F.map(e.unFix)(cata(alg)))

vvviiimmm

def almostCata(evaluator: (ExpressionF[Int] => Int))(e: Fix[ExpressionF]): Int =
   evaluator(Functor[ExpressionF].map(e.unFix)(almostCata(evaluator)))

vvviiimmm

def almostCata(evaluator: (ExpressionF[Int] => Int), e: Fix[ExpressionF]): Int = 
  evaluator(e.unFix) // won't compile