RecursionSchemes.scala

import cats.Functor // scalaz would work as well

// 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 {
      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) // 21