Catamorphim with F-Algebra, Fix and, Functor

cata.sc

// Non recursive data structure
trait Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

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 {
    case ValueF(v)    => ValueF(v)
    case AddF(e1, e2) => AddF(f(e1), f(e2))
    case MultF(e1, e2) => MultF(f(e1), f(e2))
  }
}

// Evaluation function
def evalExprF(e: ExpressionF[Int]): Int = e match {
  case ValueF(v) => v
  case AddF(e1, e2) => e1 + e2
  case MultF(e1, e2) => e1 * e2
}

// Fix data structure
final case class Fix[F[_]](unFix: F[Fix[F]])

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

// Example expression and evaluation
val someExpression: Fix[ExpressionF] =
  Fix(MultF(
    Fix(AddF(
      Fix(ValueF(1)),
      Fix(ValueF(2)))),
    Fix(AddF(
      Fix(ValueF(3)),
      Fix(ValueF(4))))))

val twentyOne = cata(evalExprF)(someExpression)

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
  case AddF(e1, e2) => "(" ++ e1 ++ " " ++ e2 ++ ")"
  case MultF(e1, e2) => e1 ++ e2
}

val algebra2: Algebra[ExpressionF, Boolean] = {
  case ValueF(_) => true
  case AddF(e1, e2) => e1 || e2
  case MultF(e1, e2) => e1 && e2
}

val alwaysTrue = cata(algebra2)(someExpression)