cata.scala

package fix

import cats._

object fix {
  trait ExprF[A]
  case class Const[A](value: Int) extends ExprF[A]
  case class Add[A](left: A, right: A) extends ExprF[A]
  case class Mul[A](left: A, right: A) extends ExprF[A]

  case class Fix[F[_]](value: F[Fix[F]])

  type Expr = Fix[ExprF]

  val const: Expr = Fix(Const[Expr](12))
  val testExpr: Expr =
    Fix(Mul[Expr](
      Fix(Add[Expr](Fix(Const(2)), Fix(Const(3)))),
      Fix(Const(4))
    ))

  implicit def exprFFunctor =
    new Functor[ExprF] {
      def map[A, B](fa: ExprF[A])(eval: A => B): ExprF[B] =
        fa match {
          case Const(i) => Const(i)
          case Add(left, right) => Add(eval(left), eval(right))
          case Mul(left, right) => Mul(eval(left), eval(right))
        }
    }

  val alg: ExprF[Int] => Int = {
    case Const(i) => i
    case Add(x, y) => x + y
    case Mul(x, y) => x * y
  }

  type Algebra[F[_], A] = F[A] => A
  type ExprInitAlg = Algebra[ExprF, Fix[ExprF]]

  def unfix[F[_]](f: Fix[F]): F[Fix[F]] =
    f match {
      case Fix(x) => x
    }

  def cata[F[_], A](alg: F[A] => A)(implicit F: Functor[F]): Fix[F] => A = { fx =>
    val un = unfix(fx)
    val mapped = F.map(un)(cata(alg))
    alg(mapped)
  }

  val eval = cata(alg)
  val res: Int = eval(testExpr) // 20

}