Stack safe hylomorphism using cats' lazy eval

hylo.sc

// Look up ammonite if you're wondering what this syntax is
import $ivy.`org.typelevel::cats-core:1.0.0-MF`

import cats._
import cats.syntax.functor._
import cats.syntax.traverse._

sealed trait Nat[+A]
case object Zero extends Nat[Nothing]
case class Succ[A](a : A) extends Nat[A]

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

implicit val traverseNat : Traverse[Nat] = new Traverse[Nat]{
  override def traverse[G[_], A, B](fa : Nat[A])(f: A => G[B])(implicit G: Applicative[G]) : G[Nat[B]] =
    fa match {
      case Zero => G.pure(Zero)
      case Succ(a) => G.map(f(a))(Succ.apply _)
    }

  override def foldRight[A, B](fa: Nat[A],lb: Eval[B])(f: (A, Eval[B]) => Eval[B]): Eval[B] =
    fa match {
      case Zero => lb
      case Succ(a) => f(a, lb)
    }

  override def foldLeft[A, B](fa: Nat[A],b: B)(f: (B, A) => B): B =
    fa match {
      case Zero => b
      case Succ(a) => f(b, a)
    }
  }

val ToInt : Algebra[Nat, Int] = {
  case Succ(i) => i + 1
  case Zero => 0
}

val FromInt : Coalgebra[Nat, Int] = {
  case i if i > 0 => Succ(i - 1)
  case i => Zero
}

// matryoshka's hylo is not stack safe. This one is (I have no idea about the memory footprint though)
// also, this is a weaker version, since traverse is more powerful than functor ... perhaps there's a
// way to require only a functor, but don't think I'm smart enough to solve this. 
def hylo[F[_] : Traverse, A, B](fold : Algebra[F, B], unfold : Coalgebra[F, A])(a : A) : Eval[B] = Eval.defer {
  val fa : F[A] = unfold(a)
  val efb : Eval[F[B]] = fa traverse hylo(fold, unfold)
  val eb  : Eval[B]    = efb map fold
  eb
}


// for context, this is pretty much matryoshka's implementation,
//  and it's probably the most beautiful piece of code I've ever seen
def unsafeHylo[F[_] : Functor, A, B](fold : Algebra[F, B], unfold : Coalgebra[F, A])(a : A) : B =
  fold(unfold(a) map unsafeHylo(fold, unfold))


println(hylo(ToInt, FromInt)(1000000).value) // unsafeHylo usually blows up somewhere between 800 and 1000