RecursionSchemes.scala http://slides.com/zainabali_/peeling_the_banana#/

RecursionSchemes.scala

import cats.Functor
import scala.language.higherKinds

object L {
  sealed trait List
  case object Nil extends List
  case class Cons(head: Int, tail: List) extends List

  // Recursive collapse

  def multiply: List => Int = {
    case Nil => 1
    case Cons(i, t) => i * multiply(t)
  }

  def length: List => Int = {
    case Nil => 0
    case Cons(_, t) => 1 + length(t)
  }
}

object LCata {
  import L.{List, Nil, Cons}

  def foldList[A](onNil: A, onCons: (Int, A) => A): List => A = {
    case Nil => onNil
    case Cons(i, t) => onCons(i, foldList(onNil, onCons)(t))
  }

  // catamorphisms
  def multiply: List => Int = foldList[Int](1, _ * _)
  def length: List => Int = foldList[Int](0, (_, len) => len + 1)
}

object T {
  // Recursive collapse
  sealed trait Tree
  case class Leaf(value: Int) extends Tree
  case class Node(left: Tree, right: Tree) extends Tree

  def foldTree[A](onLeaf: Int => A, onNode: (A, A) => A): Tree => A = {
    case Leaf(i) => onLeaf(i)
    case Node(l, r) => onNode(foldTree(onLeaf, onNode)(l), foldTree(onLeaf, onNode)(r))
  }

  def sum: Tree => Int = foldTree[Int](identity, _ + _)
  def countLeaves: Tree => Int = foldTree[Int](_ => 1, _ + _)
}

object LF {
  // Higher Kinded Types
  sealed trait ListF[A]
  case class NilF[A]() extends ListF[A]
  case class ConsF[A](head: Int, a: A) extends ListF[A]

  import L.{List, Nil, Cons}

  def in: ListF[List] => List = {
    case NilF() => Nil
    case ConsF(h, t) => Cons(h, t)
  }

  def out: List => ListF[List] = {
    case Nil => NilF()
    case Cons(h, t) => ConsF(h, t)
  }

  object instances {
    implicit val listFFunctor: Functor[ListF] = new Functor[ListF] {
      def map[A, B](fa: ListF[A])(f: A => B): ListF[B] = fa match {
        case NilF() => NilF()
        case ConsF(h, a) => ConsF(h, f(a))
      }
    }
  }
}

object ACH {
  import L.{List, Nil, Cons}
  import LF.{ListF, NilF, ConsF}
  import LF.instances._

  type Algebra[F[_], A] = F[A] => A
  type Coalgebra[F[_], A] = A => F[A]

  // Catamorphism
  def cata[F[_], R, A](algebra: Algebra[F, A], out: R => F[R])(r: R)(implicit F: Functor[F]): A =
    algebra(F.map(out(r))(cata(algebra, out)))

  // Anamorphism
  def ana[F[_], R, A](coalgebra: Coalgebra[F, A], in: F[R] => R)(a: A)(implicit F: Functor[F]): R =
    in(F.map(coalgebra(a))(ana(coalgebra, in)))

  // Hilymorphism
  def hylo[F[_], A, B](coalgebra: Coalgebra[F, A], algebra: Algebra[F, B])(a: A)(implicit F: Functor[F]): B =
    algebra(F.map(coalgebra(a))(hylo(coalgebra, algebra)))

  // ListF[List] => List
  def in: Algebra[ListF, List] = {
    case NilF() => Nil
    case ConsF(h, t) => Cons(h, t)
  }

  // List => ListF[List]
  def out: Coalgebra[ListF, List] = {
    case Nil => NilF()
    case Cons(h, t) => ConsF(h, t)
  }

  //
  // catamorphism
  //

  def multiplyAlgebra: Algebra[ListF, Int] = {
    case NilF() => 1
    case ConsF(h, i) => h * i
  }

  def multiply: List => Int = cata(multiplyAlgebra, out)

  //
  // anamorphism
  //

  def rangeCoalgebra: Coalgebra[ListF, Int] =
    n => if (n > 0) ConsF(n, n - 1) else NilF()

  def range: Int => List = ana(rangeCoalgebra, in)

  //
  // hylomorphism
  //

  def factorial: Int => Int =
    n => if (n > 0) n * factorial(n - 1) else 1

  def factorialHylo: Int => Int =
    hylo(rangeCoalgebra, multiplyAlgebra)
}

object F {
  import LF._

  // Removing boilerplate

  case class Fix[F[_]](unfix: F[Fix[F]])
  def in: ListF[Fix[ListF]] => Fix[ListF] = Fix(_)
  def out: Fix[ListF] => ListF[Fix[ListF]] = _.unfix
}

object Test {
  import L.{Nil, Cons}
  import T.{Leaf, Node}
  import LF.{ListF, ConsF, NilF}

  def lcata() = {
    val z = Cons(1, Cons(2, Cons(3, Nil)))
    println((z, LCata.multiply(z), LCata.length(z)))
  }

  def t() = {
    val z = Node(Leaf(1), Node(Leaf(2), Leaf(4)))
    println((z, T.sum(z), T.countLeaves(z)))
  }

  def lf() = {
    val a = ConsF(1, "foo")
    val b = ConsF(1, ConsF(2, ConsF(3, NilF())))

    println((a, b))
  }

  def ach() = {
    val z = Cons(1, Cons(3, Cons(5, Nil)))
    println(z)

    println(ACH.multiply(z))
    println(ACH.range(5))

    println(ACH.factorial(10))
    println(ACH.factorialHylo(10))
  }

  def rb() = {
    import F._
    val z = Fix(ConsF(1, Fix(ConsF(2, Fix(ConsF(3, Fix[ListF](NilF())))))))
    println(z)
  }
}

object M {
  // http://slides.com/zainabali_/peeling_the_banana#/29

  import matryoshka._
  import matryoshka.patterns._

  val rangeCoalgebra: Coalgebra[ListF[Int, ?], Int] =
    n => if (n > 0) ConsF(n, n - 1) else NilF()

  val multiplyAlgebra: Algebra[ListF[Int, ?], Int] = {
    case NilF() => 1
    case ConsF(h, i) => h * i
  }

  val factorialHylo: Int => Int =
    hylo(_)(multiplyAlgebra, rangeCoalgebra)

  def factorial: Int => Int =
    n => if (n > 0) n * factorial(n - 1) else 1

  def test0() = {
    val factorials = (1 to 10).map(n => (n, factorial(n)))
    factorials.map(x => assert(x._2 == factorialHylo(x._1)))
  }
}

object Main extends App {
  M.test0
}