Recursion.scala

package recursion2

import scalaz.Free._
import slamdata.Predef._
import matryoshka._
import matryoshka.data._
import matryoshka.implicits._
import org.scalatest.FunSuite

import scalaz._

sealed trait Expr[A]
case class IntW[A](value: Int) extends Expr[A]
case class Plus[A](x: A, y: A) extends Expr[A]
case class Times[A](x: A, y: A) extends Expr[A]
case class Abs[A](x:A) extends Expr[A]


class Recursion2 extends FunSuite {


  //using Matryoshka we can't abstract the recursion.

  //to evaluate, we just need a algebra, a function from Expr[_] to Int

  val evalExpr:Algebra[Expr,Int] = {
    case IntW(value) => value
    case Plus(a,b) => a + b
    case Times(a,b) => a * b
    case Abs(a) => if (a > 0) - a else a
  }

  //to use the algebra, we need to define functor on the structure :

  implicit val exprFunctor: Functor[Expr] = new Functor[Expr] {
    def map[A, B](expr: Expr[A])(f: A => B): Expr[B] = expr match {
      case IntW(v) => IntW(v)
      case Plus(x, y) => recursion2.Plus(f(x), f(y))
      case Times(x, y) => Times(f(x), f(y))
      case Abs(x) => Abs(f(x))
    }
  }

  import Fix._   // to use the Fix point (we could use Mu or Nu as well)


  //helper method
  def intW(value: Int):Fix[Expr] = Fix(IntW(value))
  def times(x: Fix[Expr], y: Fix[Expr]): Fix[Expr] = Fix(Times(x, y))
  def plus(x: Fix[Expr], y: Fix[Expr]): Fix[Expr] = Fix(Plus(x,y))
  def abs(x: Fix[Expr]): Fix[Expr] = Fix(Abs(x))

  test("1 + 1") {
    val expr: Fix[Expr] = plus(intW(1), intW(1))
    //Fix[Expr] = Expr[Fix[Expr]]

    //the we use cata to apply the algebra

    val res:Int = expr.cata(evalExpr)

    assert(res == 2)
  }

  test("1 * 2 + 1") {
    val expr: Fix[Expr] = plus(times(intW(1), intW(2)), intW(1))

    assert(3 == expr.cata(evalExpr))
  }

  //The advantage of using an algebra is reuse, we don't need to redefine the way to dive into the structure

  val showAlgebra: Algebra[Expr,String] = {
    case IntW(value) => value.toString
    case Plus(a,b) => s"($a + $b)"
    case Times(a,b) => s"($a * $b)"
    case Abs(a) => s"|$a|"
  }

  test("show : 1 * 2 + |-1|") {


    val expr:Fix[Expr] = plus(times(intW(1),intW(2)),abs(intW(-1)))

    assert(expr.cata(showAlgebra) == "((1 * 2) + |-1|)")
  }

  //But that's doesn't work out of the box for large structure
  test("large structure") {
    //...
  }

  //to work on large structure, we need to use the Trampoline technique
  //good news, we don't need to encode directly the Trampoline inside our logic


  //we need more powerfull capabilities on Expr, to generalize folding operation
  //Traverse is more powerful than a Functor
  //weaker than an Applicative (you don't need Point)

  implicit val exprTraverse: Traverse[Expr] = new Traverse[Expr] {
    override def traverseImpl[G[_], A, B](fa: Expr[A])(f: (A) => G[B])(implicit app: Applicative[G]): G[Expr[B]] = fa match {
      case IntW(value) => app.point(IntW(value))
      case Plus(x,y) => app.apply2(f(x), f(y))(recursion2.Plus(_,_))
      case Times(x,y) => app.apply2(f(x),f(y))(Times(_,_))
      case Abs(x) => app.map(f(x))(Abs(_))
    }
  }

  test("1 + 2 + ... + 100000") {

    //having traverse on Expr, we can lift cata (implemented using hylo) in order to use Trampoline

    def cataTrampoline[E[_],A](t: Fix[E])(f: Algebra[E, A])(implicit BT: Traverse[E]):Trampoline[A] = {
      //with regular cata being :
      //t.hylo[E,A](f, x => x.unFix)
      t.hyloM[Trampoline,E,A](
        x => Trampoline.delay(f(x)),
        x => Trampoline.delay(x.unFix))
    }

    val expr:Fix[Expr] = (1 to 100000).map(intW).reduce(plus)


    val res:Trampoline[Int] = cataTrampoline(expr)(evalExpr)

    assert(res.run == (1 to 100000).sum)

    //println(cataTrampoline(expr)(showAlgebra).run)
  }
  
}