julian-klode/bsc-thesis-code — pull request #6 by yfcai (2014-09-12 10:16:28+00:00)
Title: Make geq not overflow the stack on long lists via scalaz trampoline

1. The `RProd` case of `geq` is not a tail call.

2. Scalac does not recognize a generic function calling itself with a different type parameter as tail recursion.

@tailrec final def f[A]: Int = f[Int] // does not compile

3. One way to get around (2) is to reimplement the call stack on the heap. The technique is called _trampolining_. [This blog post][1] explains it. The section "Trampolines of trampolines" is relevant for dealing with (1).

Scalaz supports trampolines. Here's a [usage example][2]. Here's the [implementation code][3] showing available methods with comments about what they do.

[1]: http://apocalisp.wordpress.com/2011/10/26/tail-call-elimination-in-scala-monads/

[2]: https://github.com/scalaz/scalaz/blob/series/7.2.x/example/src/main/scala/scalaz/example/TrampolineUsage.scala

[3]: https://github.com/scalaz/scalaz/blob/series/7.2.x/core/src/main/scala/scalaz/Free.scala