Some toy examples of matryoshka use

Presentation.scala

package presentation

import matryoshka.data.Fix

import scalaz.Functor

object Presentation extends App {

  // 1 : abstract recursion away

  sealed trait AST[+A]
  case class Add[A](left: A, right: A) extends AST[A]
  case class Mul[A](left: A, right: A) extends AST[A]
  case class Lit(value: Long)          extends AST[Nothing]
  case class Var(s: Symbol)            extends AST[Nothing]

  // 1.1 : syntax

  object syntax {

    object lit {
      def apply(v: Long): Fix[AST] = Fix[AST](Lit(v))

      def unapply(arg: Fix[AST]): Option[Long] = arg match {
        case Fix(Lit(a)) => Some(a)
        case _           => None
      }
    }

    object add {
      def apply(left: Fix[AST], right: Fix[AST]): Fix[AST] = Fix[AST](Add(left, right))

      def unapply(arg: Fix[AST]): Option[(Fix[AST], Fix[AST])] = arg match {
        case Fix(Add(a, b)) => Some((a, b))
        case _              => None
      }
    }

    object mul {
      def apply(left: Fix[AST], right: Fix[AST]) = Fix[AST](Mul(left, right))

      def unapply(arg: Fix[AST]): Option[(Fix[AST], Fix[AST])] = arg match {
        case Fix(Mul(a, b)) => Some((a, b))
        case _              => None
      }
    }

    object varx {
      def apply(s: Symbol): Fix[AST] = Fix[AST](Var(s))

      def unapply(arg: Fix[AST]): Option[Symbol] = arg match {
        case Fix(Var(s)) => Some(s)
        case _           => None
      }
    }
  }

  // 2 : implement a functor for our model

  implicit val astFunctor: Functor[AST] = new Functor[AST] {
    override def map[A, B](fa: AST[A])(f: A => B) = fa match {
      case Add(a, b)         => Add(f(a), f(b))
      case Mul(a, b)         => Mul(f(a), f(b))
      case lit @ Lit(_)      => lit
      case variable @ Var(_) => variable
    }
  }

  // 3 : implement logic, one layer at a time

  type Tree = Fix[AST]
  import syntax._

  val ToString: AST[String] => String = {
    case Lit(i)           => i.toString
    case Add(left, right) => s"($left + $right)"
    case Mul(left, right) => s"($left * $right)"
    case Var(x)           => x.name
  }

  def derive(variable: Symbol): AST[(Tree, Tree)] => Tree = {
    case Mul((x, dx), (y, dy)) => add(mul(x, dy), mul(dx, y))
    case Add((_, dx), (_, dy)) => add(dx, dy)
    case Var(`variable`)       => lit(1)
    case Var(_)                => lit(0)
    case Lit(_)                => lit(0)
  }

  def partiallyApply(variable: Symbol, value: Long): Tree => Tree = {
    case varx(`variable`) => lit(value)
    case other            => other
  }

  val add0Rule: Tree => Tree = {
    case add(lit(0), a) => a
    case add(a, lit(0)) => a
    case other          => other
  }

  val mul1Rule: Tree => Tree = {
    case mul(a, lit(1)) => a
    case mul(lit(1), a) => a
    case other          => other
  }

  val mul0Rule: Tree => Tree = {
    case mul(_, b @ lit(0)) => b
    case mul(b @ lit(0), _) => b
    case other              => other
  }

  val addSameRule: Tree => Tree = {
    case add(a, b) if a == b => mul(lit(2), a)
    case other               => other
  }

  // 4 : benefit

  // (x + 1) * (y + 2) + 3
  val exprXY = add(
    mul(
      add(
        varx('x),
        lit(1)
      ),
      add(
        varx('y),
        lit(2)
      )
    ),
    lit(3)
  )

  import matryoshka.Birecursive.ops._

  val trim = mul1Rule andThen add0Rule andThen mul0Rule andThen addSameRule

  val exprY: Tree = exprXY.transCataT(partiallyApply('x, 0) andThen trim)

  val exprXYdX: String = exprXY.para(derive('x)).transCataT(trim).cata(ToString)

  println(exprXYdX)
  // y + 2

}