stackoverflow on fib(1500)

[chenharryhua]

Running the example on the homepage triggers stack overflow exception.

[andyscott]

This is expected (and unfortunately not easily solved!). The recursion schemes using kernel.hylo all consume a bit of stack for each level of structure. fib(x) first encodes x as a Peano number with x levels of structure, so fib(1500) results in an attempted 1500 calls deep into the stack.

[sellout]

You can trampoline the hylo by using hyloM[Eval], with Eval.delay in your algebra & coalgebra.

As an aside, there doesn’t seem to be a link to the site from the README.

[chenharryhua]

@sellout seems it doesn't work: (matryoshka + scalaz)

 def expr[T](n: Int)(implicit T: Corecursive.Aux[T, Option]): Trampoline[T] = {
    n match {
      case 0 => Trampoline.delay(none[T].embed)
      case m => Trampoline.suspend(expr(m - 1).map(some(_).embed))
    }
  }
  val e = expr[Fix[Option]](500).cataM[Trampoline, Int] { x => Trampoline.done(0) }
  println(e.run)

e.run throws stack overflow exception.

[sellout]

@chenharryhua You can’t do it with cataM, only with hyloM. This is because cataM necessarily uses Monad.pure to traverse out to the leaves of the structure, and pure for Trampoline is eager, not delay.

So you have to use hyloM, even if it’s just to do a => Trampoline.delay(a.project).

[chenharryhua]

Thanks, @sellout . very helpful. by using hyloM, the stack overflow issue is gone. I wonder if it is because holyM does not build up the structure at all.

[johnynek]

Note, cats has the Defer type class which generalizes Eval.defer to the many structures that support it. You could make a variant of cataM that uses defer with pure that should be stack safe.

[andyscott]

This sounds great! Defer is a new addition (by you?) if I'm not mistaken?

[johnynek]

It is. It may be useful in a few other locations to make generic stack safety work. Might be good to collect examples of blowing the stack and try to burn them down.

[andyscott]

But... were you offering to submit a pull request to leverage defer? 😁

[niqdev]

Hello! Thanks for the great lib, I'm pretty new to recursion schema and all the fancy names and I'm just trying to poke around...

Since matryoshka looks like it's EOL I was trying to re-implement the examples using droste and eventually open a pr (if you think it would be useful), but I hit a StackOverflowError in the simplest example 😔

Would you mind to give me some hints on how to fix it?

My understanding is that Applicative[G].pure(Zero) is the issue here, how would you recommend to fix it in a nice way? Should I use Sync?

Thanks in advance

import cats.{ Applicative, Functor, Traverse }
import higherkindness.droste.data.Fix
import higherkindness.droste.util.DefaultTraverse
import higherkindness.droste.{ Algebra, Coalgebra, scheme }

// https://github.com/precog/matryoshka/blob/master/tests/shared/src/test/scala/matryoshka/example/nat.scala
object nat {

  import cats.syntax.functor.toFunctorOps

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

  implicit val natFunctor: Functor[Nat] = new Functor[Nat] {
    override def map[A, B](fa: Nat[A])(f: A => B): Nat[B] =
      fa match {
        case Zero           => Zero
        case Succ(previous) => Succ(f(previous))
      }
  }

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

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

  // required by hyloM
  implicit val natTraverse: Traverse[Nat] = new DefaultTraverse[Nat] {
    override def traverse[G[_]: Applicative, A, B](fa: Nat[A])(f: A => G[B]): G[Nat[B]] = fa match {
      case Zero           => Applicative[G].pure(Zero) // <<<<<<<<<< cause of StackOverflowError
      case Succ(previous) => f(previous) map (Succ(_))
    }
  }

  val intToNat: Int => Fix[Nat]          = scheme.ana(toNat)
  val natToInt: Fix[Nat] => Int          = scheme.cata(toInt)
  val intToNatToInt: Int => Int          = scheme.hylo(toInt, toNat)
  val intToNatToIntStackSafe: Int => Int = scheme.hyloM(toInt.lift, toNat.lift)
}

and here the tests

import org.scalacheck.Gen
import org.scalatest.matchers.should.Matchers
import org.scalatest.wordspec.AnyWordSpecLike
import org.scalatestplus.scalacheck.ScalaCheckPropertyChecks

final class NatProp extends AnyWordSpecLike with ScalaCheckPropertyChecks with Matchers {

  "Nat" should {
    // expected to throw StackOverflowError
    "verify hylo" in {
      forAll(Gen.chooseNum(0, Int.MaxValue)) { n => intToNatToInt(n) shouldBe natToInt(intToNat(n)) }
    }
    // should work when fixed
    "verify hyloM" in {
      forAll(Gen.chooseNum(0, Int.MaxValue)) { n => intToNatToIntStackSafe(n) shouldBe n }
    }
  }
}