Trying out recursive schemes with matryoshka scala library

RecursionSchemes.scala

//Notes and code from this talk https://www.youtube.com/watch?v=IlvJnkWH6CA

object RecursiveSchemes extends App{
  object one {
    sealed trait Exp
    final case class IntValue(v:Int) extends Exp
    final case class DecValue(v:Double) extends Exp
    final case class Sum(exp1:Exp, exp2:Exp) extends Exp
    final case class Multiply(exp1:Exp, exp2:Exp) extends Exp
    final case class Divide(exp1:Exp, exp2:Exp) extends Exp
    final case class Square(exp:Exp) extends Exp

    val evaluate:Exp => Double = {
      case IntValue(v) => v.toDouble
      case DecValue(v) => v
      case Sum(e1,e2) => evaluate(e1) + evaluate(e2)
      case Multiply(e1,e2) => evaluate(e1) * evaluate(e2)
      case Square(e) =>
        val v = evaluate(e)
        v * v
      case Divide(e1,e2) => evaluate(e1) / evaluate(e2)
    }

    val mkString: Exp => String = {
      case IntValue(v) => v.toString()
      case DecValue(v) => v.toString()
      case Sum(e1,e2) => s"( ${mkString(e1)} + ${mkString(e2)})"
      case Multiply(e1,e2) => s"( ${mkString(e1)} * ${mkString(e2)})"
      case Square(e) => s"( ${mkString(e)})^2"
      case Divide(e1,e2) => s"( ${mkString(e1)} / ${mkString(e2)})"
    }

    /*
     Mixing two concernes
     1> evaluating or mkString (business call)
     2> And going to the leaf to fetch the values (recursion part)
     */

    //What if we want to optimize before evaluation
    val optimize: Exp => Exp = {
      case Multiply(e1,e2) if e1 == e2 => Square(optimize(e1))
      case IntValue(v) => IntValue(v)
      case DecValue(v) => DecValue(v)
      case Sum(e1,e2) => Sum(optimize(e1) ,optimize(e2))
      case Square(e) => Square(optimize(e))
      case Divide(e1,e2) => Divide(optimize(e1),optimize(e2))
    }
    //you still need to recursion along with the optimize

  }

  val exp1 = one.Multiply(
    one.Sum(
      one.IntValue(10),
      one.DecValue(2.5)
    ),
    one.Divide(
      one.DecValue(5.2),
      one.Sum(one.IntValue(10),one.IntValue(5)
      )
    )
  )
  println("*" * 50)
  println(one.evaluate(exp1))
  println(one.mkString(exp1))
  println("*" * 50)

  /*
   What if the recursive traversing is done for you
   and the "business" or the functions deal only with the values
   As we can see the process itself is redundant in all the operations like 
   evaluation, mking a string or optimization

   So we need someone else to do this travesing for us get the values 
   and our functions can just execute those functions, sounds good!!
   i.e. our functions must just work on values

   */
  object two {
    //Inorder to do that with the current structure we need to use paramitricity
    sealed trait Exp[A]
    final case class IntValue[A](v:Int) extends Exp[A]
    final case class DecValue[A](v:Double) extends Exp[A]
    final case class Sum[A](exp1:A, exp2:A) extends Exp[A]
    final case class Multiply[A](exp1:A, exp2:A) extends Exp[A]
    final case class Divide[A](exp1:A, exp2:A) extends Exp[A]
    final case class Square[A](exp:A) extends Exp[A]

    val exp:one.Exp = one.Sum(
      one.IntValue(10),
      one.IntValue(5)
    )
    /*
     
    val exp2:Exp[?] = Sum[?](
      IntValue[?](10),
      IntValue[?](5)
    )

     val exp2:Exp[?] = Sum[?](
      IntValue[Unit](10),
      IntValue[Unit](5)
    )

     val exp2:Exp[?] = Sum[Exp[Unit]](
      IntValue[Unit](10),
      IntValue[Unit](5)
    )
     
     */

    val expp:Exp[Exp[Unit]] = Sum[Exp[Unit]](
      IntValue[Unit](10),
      IntValue[Unit](5)
    )

    //lets take one more example
    val exp1:one.Exp = one.Divide(
      one.DecValue(5.2),
      one.Sum(
        one.IntValue(10),
        one.IntValue(5)
      )
    )

    //and the generic type becomes something like this
    val exp2:Exp[Exp[Exp[Unit]]] = Divide(
      DecValue[Exp[Unit]](5.2),
      Sum[Exp[Unit]](
        IntValue[Unit](10),
        IntValue[Unit](5)
      )
    )

    /*
     It is difficult to represent something like this
     val exp:Exp[???] = evaluate(someExpression)

     To fix this issue we have an intresting data type called Fix
     */

  }

  object three{
    case class Fix[F[_]](unFix:F[Fix[F]])

    /*
     Now lets convert the previous expressions to Fix
     */
    import two.{Exp => Ex, _}

    val ex1:Ex[Ex[Unit]] =
      Sum[Ex[Unit]](
        IntValue[Unit](10),
        IntValue[Unit](5)
      )

    val ex2:Fix[Ex] =
      Fix(Sum[Fix[Ex]](
        Fix(IntValue(10)),
        Fix(IntValue(5))
      ))

    val ex3:Fix[Ex] = Fix(
      Divide(
        Fix(DecValue(5.2)),
        Fix(
          Sum(
            Fix(IntValue(10)),
            Fix(IntValue(5))
          )
        )
      ))

    //And now val exp:Fix[Exp] = evaluate(someExpression) is quite possible and simple

  }
    //Lets remember why we were doing all this.
    //We were doing this to do seperation of concenrns, recusive traversing and business

    //there are different ways to seperate the concerns the way of traversing,  one of the way is called catamorphism

    //For catamorphism to work we need two things
    //1> Functor
    //2> function (F-Algebra)

    import two.{Exp => Ex,_}

    implicit val expFunctor:Functor[Ex] = new Functor[Ex] {
      override def map[A, B](exp: Ex[A])(f: A => B): Ex[B] = exp match {
        case IntValue(v) => IntValue(v)
        case DecValue(v) => DecValue(v)
        case Sum(e1,e2) => Sum(f(e1) ,f(e2))
        case Multiply(e1,e2) => Multiply(f(e1),f(e2))
        case Square(e) => Square(f(e))
        case Divide(e1,e2) => Divide(f(e1),f(e2))
      }
    }

    //F-Algebra is just a function which looks something like this
    //type Algebra[F[_],A] = F[A] => A
    import matryoshka.data.Fix
    import matryoshka._
    import matryoshka.implicits._

    val evaluate: Algebra[Ex, Double] = {
      case IntValue(v) => v.toDouble
      case DecValue(v) => v
      case Sum(e1,e2) => e1 + e2
      case Multiply(e1,e2) => e1 * e2
      case Square(e) => e * e
      case Divide(e1,e2) => e1 / e2
    }

    val eexxpp: Fix[Ex] = Fix(Divide(
      Fix(DecValue(5.2)),
      Fix(Sum(
        Fix(IntValue(10)),
        Fix(IntValue(2))
      ))
    ))


  println("*"*50)
  println("Lets use cata one of the functions from library to travesing")
  println("*"*50)
  println(eexxpp.cata(evaluate))

  //F-Algebra for mkString and run cata again

  val mkString: Algebra[Ex, String] = {
    case IntValue(v) => v.toString()
    case DecValue(v) => v.toString()
    case Sum(e1,e2) => s"($e1 + $e2)"
    case Multiply(e1,e2) => s"($e1 * $e2)"
    case Square(e) => s"($e)^2"
    case Divide(e1,e2) => s"($e1 / $e2)"
  }

  println("*"*50)
  println(eexxpp.cata(mkString))

  //How is it different from previous solution
  //1. Totality
  //2. that means the stack will never blows up. The recursion mechinery takes case of it for you.
  //3. Algebra is more focused and simplified so less chances of getting an error for example in optimize operation below

  val optimize:Algebra[Ex, Fix[Ex]] = {
    case Multiply(Fix(a1), Fix(a2)) if(a1 == a2) => Fix(Square(Fix(a1)))
    case other => Fix(other)
  }

  //unlike the previous optimize where there were likely chances of missing a optimize and the code still have compiled.

  /*
   There are other recusive schemes
   Catamorphism we get a value from a structure
   --> type Algebra[F[_],A] = F[A] => A 
   Anamorphisms we get a structure from a value
   --> type Coalgebra[F[_], A] = A => F[A]
   Hylomorphism is a combination of above two
   --> Anamorphisms followed by Catamorphism
   --> Constructs and then deconstructs a structure from a value
   */

}