It can't be done 🙂 (at least not on a single JVM thread with limited stack).
TL;DR
The combination of requirements (a), (b), (c) inevitably leads to pathological solutions (see "Inter-Thread Recursion" below as well as the Addendum).
In the signature
def foldRight[T, U](base: U)(f: (T, => U) => U)(as: Seq[T]): U
the type (T, => U) => U means that
- the first invocation of
f cannot return until all the subsequent invocations of f have returned;
- each invocation of
f must be able to hold some data in its stack frame from the beginning to the end;
- therefore, you need an unbounded number of stack-frames for
f that coexist simultaneously
- if you limit the maximum stack-depth without limiting the number of stack-frames, you're forced to create an unbounded number of threads.
No amount of tricks with trampolines will help, because you cannot change the way causality works.
The above argument leads to a working implementation (see "Inter-thread recursion" section below). However, spawning thousands of threads as mere containers for stack frames is very unnatural, and indicates that the signature should be changed.
Overview
Instead of just giving the code snippet with the ready solution, we want to explain how to arrive at it. Indeed, we want to arrive at two different solutions:
- First, by clinging to the signature (a), we arrive at the solution "Inter-Thread Recursion" that satisfies (a), (b) and (c). In the process, however, we will see why this is unacceptable, so we will drop the requirement (a).
- Once we dropped the requirement (a), we want to gradually arrive at a better solution based on
TailRec / Eval.
The rest of this answer is structured as follows:
We first take a look at some failed approaches, just to understand the problem better, and to collect some requirements:
- The "Naive Recursion" approach will show how one can successfully "skip the infinity" (b), but fail with a stack overflow (!c).
- The "Failed TailRec" approach will show how one can circumvent the stack overflow (c), while failing to "skip the infinity" (!b).
The "Inter-Thread Recursion" section presents the solution that formally satisfies all three requirements ((a), (b), (c)) of the question, but spawns and unbounded number of threads. Since spawning multiple threads is not a viable solution, this forces us to give up the original signature.
Then we investigate alternative signatures:
- "Returning Either[U => U, U]" will show a simple way to satisfy (b) and (c), but it will sometimes force us to construct long lists of closures for no good reason.
- "No Postprocessing" will show how to satisfy (b) and (c) for certain problems without a long list of closures, but it will also demonstrate a significant loss in expressiveness, thus motivating...
- ... a return to "TailRec Done Properly", which solves (b) and (c), does not create any unnecessarily large auxiliary data structures, and retains full expressiveness;
- Finally, as a bonus, in "Eval" we mention that
TailRec can be replaced by cats.Eval.
Naive Recursion
def foldRight[T, U](base: U)(f: (T, => U) => U)(as: Seq[T]): U = {
as match {
case head +: next => f(head, foldRight(base)(f)(next))
case _ => base
}
}
The naive recursion attempted in the first paragraph of the question (and also mentioned in numerous blogs and articles, such as here) has two seemingly contradictory properties:
- It "can cope with infinite streams", but at the same time
- it blows up with a stack overflow on long (finite) lists.
There is no paradox here. The first property means that if the solution can be determined by looking just at the few elements at the beginning of a sequence, the naive-recursive foldRight can skip the infinite number of elements in the tail. However, the second property means that the solution cannot look at too many elements at the beginning of the sequence.
The first property is the good part of this solution: we definitely should give f the possibility to skip the rest of the sequence once it has processed the data that it actually needed.
Failed TailRec
In the comments to the question this TailRec-based solution was mentioned:
def foldRight[T, U](base: U)(f: (T, => U) => U)(as: Seq[T]): U = {
import scala.util.control.TailCalls._
@annotation.tailrec
def _foldRightCPS(fu: U => TailRec[U])(as: Seq[T]): TailRec[U] = {
as match {
case Nil => fu(base)
case head +: next => _foldRightCPS(u => tailcall(fu(f(head, u))))(next)
}
}
_foldRightCPS(u => done(u))(as).result
}
The problem here is that it does not actually work on infinite streams (because it doesn't give f the opportunity to decide whether it wants to continue or not, so it cannot "stop early", before "seeing the end of an infinite stream" - which never happens).
It is "avoiding" the problem with an unbounded number of simultaneously coexisting stack frames of f by refusing the k-th invocation the possibility to decide whether the (k+1)-th is required or not. For finite lists, this allows to do
- the last (rightmost),
- then the second-to-last,
- third-to-last,
- ...,
- leftmost
invocation one-by-one, but if there is no "rightmost"
f to begin with, this scheme falls apart.
The good thing about this solution is the idea with TailRec trampolining. While it's insufficient on its own, it will come in handy later on (in "TailRec Done Properly").
Inter-Thread Recursion
Suppose that we don't want to make the same mistake as in the previous section: we definitely want to let f decide whether the rest of the sequence should be looked at or not.
In the introduction, we claimed that this leads to the requirement that an unbounded number of f stack frames must be able to simultaneously coexist in the memory.
To see this, we need just a single counterexample that makes it obvious that we must be able to keep an unbounded number of stack frames in memory.
Let's specialize the signature of f: (T, => U) => U for T = Boolean and U = Unit, and consider a list consisting of one million trues, followed by a single false.
Suppose that f is implemented as follows:
(t, u) => {
val x = util.Random.nextInt // this value exists at the beginning
println(x)
if (t) {
u // `f` cannot exit until we're done with the rest
}
println(x) // the value must exist until `f` returns
}
The very first invocation of f
- samples a random integer and
- stores it in its stack frame in
x;
- then it continues with
u, invoking f for the second, third, fourth... millionth time.
- once all other 999999
fs have exited, it must still have access to the x in its stack frame.
Therefore, one million random values must be stored in one million local variables x in one million stack frames, all of which must be active at the same time.
On the JVM, there is no way to take a stack frame and convert it into something else (a heap-allocated object, say).
Unless you tweak the JVM settings and allow the stack to grow indefinitely, you must limit the height of the stack. Having an unbounded number of stack frames while respecting the maximum stack height means that you need multiple stacks. In order to have multiple stacks, you need to start multiple threads.
This indeed leads to a solution that formally satisfies all three of your requirements:
def foldRight[T, U](base: U)(f: (T, => U) => U)(as: Seq[T]): U = {
// The number of active stack-frames remains bounded for each stack
val MaxFrames = 1000
// This recursively spawns multiple threads;
def interthreadRecursion(remainingSeq: Seq[T]): U = {
// a synchronized mailbox that we use to pass the result
// from the child thread to the caller
val resultFromChildThread = new java.util.concurrent.atomic.AtomicReference[U]
val t = new Thread {
def stackRec(remainingSeq: Seq[T], remainingFrames: Int): U = {
if (remainingFrames == 0) {
// Note that this happens in a different thread,
// the frames of `interthreadRecursion` belong to
// separate stacks
interthreadRecursion(remainingSeq)
} else {
remainingSeq match {
case Nil => base
case head +: next => f(head, stackRec(next, remainingFrames - 1))
}
}
}
override def run(): Unit = {
// start the stack-level recursion
resultFromChildThread.set(stackRec(remainingSeq, MaxFrames))
}
}
t.start()
t.join()
// return the result to the caller
resultFromChildThread.get()
}
// start the thread-level recursion
interthreadRecursion(as)
}
def containsElement[T](e: T)(as: Seq[T]): Boolean = {
foldRight(false)((el: T, acc) => if (el == e) true else acc)(as)
}
It keeps your foldRight signature exactly as it was (a), and it works for both your test-cases (the infinite stream without base-case (b), as well as the list with a million entries (c)).
But creating an unbounded number of threads as mere containers for stack-frames is clearly insane. Therefore, if we want to keep (b) and (c), we are forced to abandon the signature (a).
No Frameworks: Returning Either[U => U, U]
How can we modify the signature so that we can solve (b) and (c),
but without creating multiple threads?
Here is one simple and illustrative solution that gets by with a single thread, and also doesn't rely any pre-existing stack-safety/trampolining frameworks:
import util.{Either, Left, Right}
def foldRight[T, U](base: U)(f: T => Either[U => U, U])(as: Seq[T]): U = {
@annotation.tailrec
def rec(remainingAs: Seq[T], todoSteps: List[U => U]): U =
remainingAs match
case head +: tail => f(head) match
case Left(step) => rec(tail, step :: todoSteps)
case Right(done) => todoSteps.foldLeft(done)((r, s) => s(r))
case _ => todoSteps.foldLeft(base)((r, s) => s(r))
rec(as, Nil)
}
def containsElement[T](e: T)(as: Seq[T]): Boolean = {
foldRight(false)((el: T) => if (el == e) Right(true) else Left(identity))(as)
}
It works on both of your examples. The helper-method rec is obviously tail-recursive, it doesn't need any difficult-to-grasp libraries.
The change in the signature is that f is allowed to look at T and then to return an Either[U => U, U], with the Right[U] corresponding to the final result of current rec-invocation, and Left[U => U] corresponding to the case where it needs to look at the result of the tail and postprocess it in some way.
The reason why this solution works is that it creates heap-allocated closures U => U which are stashed in an ordinary List. The information that was previously held in the stack frames is moved to the heap, so there is no potential for stack overflows.
This solution has at least one drawback, though: for simple functions like containsElement, it would create a very long List[U => U] that holds just identity functions that don't do anything. Even the GC complains about it:
[warn] In the last 9 seconds, 5.043 (59.9%) were spent in GC. [Heap: 0.91GB free of 1.00GB, max 1.00GB] Consider increasing the JVM heap using `-Xmx` or try a different collector, e.g. `-XX:+UseG1GC`, for better performance.
Can we get rid of this list somehow? (let's call this new requirement (d)).
No Postprocessing
The reason why we needed a List[U => U] in the previous section is that f needs a way to "post-process" the results returned from the tail of the sequence. Since simple functions like containsElement don't actually need this, we might be tempted to experiment with simpler recursion schemes, such as the following:
/** If `f` returns `Some[U]`, then this is the result.
* If `f` returns `None`, recursively look at the tail.
*/
def collectFirst[T, U](base: U)(f: T => Option[U])(as: Seq[T]): U = {
@annotation.tailrec
def rec(remainingAs: Seq[T]): U =
remainingAs match
case head +: tail => f(head) match
case Some(done) => done
case None => rec(tail)
case _ => base
rec(as)
}
def containsElement[T](e: T)(as: Seq[T]): Boolean = {
collectFirst(false)((el: T) => if (el == e) Some(true) else None)(as)
}
Unfortunately, even though it's sufficient for containsElement, it's not as expressive as a true foldRight (see nestBrackets and foldNonassocOp in the "Full Code" section for concrete examples of functions that are not expressible through collectFirst).
Back to TailRec: TailRec Done Right
Having looked at a few other failed attempts, we are returning to TailRec:
def foldRight[T, U](base: U)(f: (T, TailRec[U]) => TailRec[U])(as: Seq[T]): U = {
def rec(remaining: Seq[T]): TailRec[U] =
remaining match
case head +: tail => tailcall(f(head, rec(tail)))
case _ => done(base)
rec(as).result
}
which can be used like this:
def containsElement[T](e: T)(as: Seq[T]): Boolean = (
foldRight[T, Boolean]
(false)
((elem, rest) => if (elem == e) done(true) else rest)
(as)
)
This satisfies (b), (c) and (d). Also note how similar it is to the naive recursion with nested helper method (see Full Code).
Full code
/** The naive recursion proposed at the beginning of the question.*/
object NaiveRecursive extends SignaturePreservingApproach:
def description = """Naive recursive (from question itself, 1st attempt)"""
def foldRight[T, U](base: U)(f: (T, => U) => U)(as: Seq[T]): U = {
as match {
case head +: next => f(head, foldRight(base)(f)(next))
case _ => base
}
}
/** This attempts to use TailRec, but fails on infinite streams */
object TailRecFromUsersScalaLangOrg extends SignaturePreservingApproach:
def description = "TailRec (from link to discussion on scala-lang.org)"
def foldRight[T, U](base: U)(f: (T, => U) => U)(as: Seq[T]): U = {
import scala.util.control.TailCalls._
@annotation.tailrec
def _foldRightCPS(fu: U => TailRec[U])(as: Seq[T]): TailRec[U] = {
as match {
case Nil => fu(base)
case head +: next => _foldRightCPS(u => tailcall(fu(f(head, u))))(next)
}
}
_foldRightCPS(u => done(u))(as).result
}
/** The solution that satisfies all properties (a), (b), (c),
* but requires multiple threads.
*/
object InterThreadRecursion extends SignaturePreservingApproach:
def description = "Inter-thread recursion"
def foldRight[T, U](base: U)(f: (T, => U) => U)(as: Seq[T]): U = {
// The number of active stack-frames remains bounded for each stack
val MaxFrames = 1000
// This recursively spawns multiple threads;
def interthreadRecursion(remainingSeq: Seq[T]): U = {
// a synchronized mailbox that we use to pass the result
// from the child thread to the caller
val resultFromChildThread = new java.util.concurrent.atomic.AtomicReference[U]
val t = new Thread {
def stackRec(remainingSeq: Seq[T], remainingFrames: Int): U = {
if (remainingFrames == 0) {
// Note that this happens in a different thread,
// the frames of `interthreadRecursion` belong to
// separate stacks
interthreadRecursion(remainingSeq)
} else {
remainingSeq match {
case Nil => base
case head +: next => f(head, stackRec(next, remainingFrames - 1))
}
}
}
override def run(): Unit = {
// start the stack-level recursion
resultFromChildThread.set(stackRec(remainingSeq, MaxFrames))
}
}
t.start()
t.join()
// return the result to the caller
resultFromChildThread.get()
}
// start the thread-level recursion
interthreadRecursion(as)
}
/** A solution that works for (b) and (c), but requires (!a). */
object ReturnEither extends SolutionApproach:
import util.{Either, Left, Right}
def description = "Return Either[U => U, U]"
def foldRight[T, U](base: U)(f: T => Either[U => U, U])(as: Seq[T]): U = {
@annotation.tailrec
def rec(remainingAs: Seq[T], todoSteps: List[U => U]): U =
remainingAs match
case head +: tail => f(head) match
case Left(step) => rec(tail, step :: todoSteps)
case Right(done) => todoSteps.foldLeft(done)((r, s) => s(r))
case _ => todoSteps.foldLeft(base)((r, s) => s(r))
rec(as, Nil)
}
def containsElement[T](e: T)(as: Seq[T]): Boolean = {
foldRight(false)((el: T) => if (el == e) Right(true) else Left(identity))(as)
}
def nestBrackets(labels: Seq[String], center: String): String =
foldRight(center)(l => Left(w => s"[${l}${w}${l}]"))(labels)
def foldNonassocOp(numbers: Seq[Int]): Int = (
foldRight
(0)
(
(n: Int) =>
if n == 0
then Right(0)
else Left((h: Int) => nonassocOp(n, h))
)
(numbers)
)
/** An overly restrictive signature that leads to expressiveness loss. */
object NoPostprocessing extends SolutionApproach:
import util.{Either, Left, Right}
def description = "No postprocessing"
def collectFirst[T, U](base: U)(f: T => Option[U])(as: Seq[T]): U = {
@annotation.tailrec
def rec(remainingAs: Seq[T]): U =
remainingAs match
case head +: tail => f(head) match
case Some(done) => done
case None => rec(tail)
case _ => base
rec(as)
}
def containsElement[T](e: T)(as: Seq[T]): Boolean = {
collectFirst(false)((el: T) => if (el == e) Some(true) else None)(as)
}
def nestBrackets(labels: Seq[String], center: String): String = ???
def foldNonassocOp(numbers: Seq[Int]): Int = ???
/** This is just to demonstrate syntactic similarity to EvalApproach */
object SyntacticallySimilarToEval extends SolutionApproach:
def description = "Syntactically analogous to Eval"
def foldRight[T, U](base: U)(f: (T, U) => U)(as: Seq[T]): U = {
def rec(remaining: Seq[T]): U =
remaining match
case head +: tail => f(head, rec(tail))
case _ => base
rec(as)
}
def containsElement[T](e: T)(as: Seq[T]): Boolean = (
foldRight[T, Boolean]
(false)
((elem, rest) => if (elem == e) true else rest)
(as)
)
def nestBrackets(labels: Seq[String], center: String): String = (
foldRight[String, String]
(center)
((label, middle) => s"[${label}${middle}${label}]")
(labels)
)
def foldNonassocOp(numbers: Seq[Int]): Int = (
foldRight[Int, Int]
(0)
(
(n, acc) =>
if n == 0
then 0
else nonassocOp(n, acc)
)
(numbers)
)
/** A `TailRec`-based solution that works */
object TailRecDoneRight extends SolutionApproach:
def description = "Ok solution with TailRec"
import util.control.TailCalls._
def foldRight[T, U](base: U)(f: (T, TailRec[U]) => TailRec[U])(as: Seq[T]): U = {
def rec(remaining: Seq[T]): TailRec[U] =
remaining match
case head +: tail => tailcall(f(head, rec(tail)))
case _ => done(base)
rec(as).result
}
def containsElement[T](e: T)(as: Seq[T]): Boolean = (
foldRight[T, Boolean]
(false)
((elem, rest) => if (elem == e) done(true) else rest)
(as)
)
def nestBrackets(labels: Seq[String], center: String): String = (
foldRight[String, String]
(center)
((label, middle) => middle.map(m => (s"[${label}${m}${label}]")))
(labels)
)
def foldNonassocOp(numbers: Seq[Int]): Int = (
foldRight[Int, Int]
(0)
(
(n, acc) =>
if n == 0
then done(0)
else acc.map(nonassocOp(n, _))
)
(numbers)
)
/** Bonus: same as "TailRec Done Right", but with `cats.Eval` */
/* requires `cats`
object EvalApproach extends SolutionApproach:
def description = "Nice solution with Eval"
import cats.Eval
def foldRight[T, U](base: U)(f: (T, Eval[U]) => Eval[U])(as: Seq[T]): U = {
def rec(remaining: Seq[T]): Eval[U] =
remaining match
case head +: tail => Eval.defer(f(head, rec(tail)))
case _ => Eval.now(base)
rec(as).value
}
def containsElement[T](e: T)(as: Seq[T]): Boolean = (
foldRight[T, Boolean]
(false)
((elem, rest) => if (elem == e) Eval.now(true) else rest)
(as)
)
def nestBrackets(labels: Seq[String], center: String): String = (
foldRight[String, String]
(center)
((label, middle) => middle.map(m => (s"[${label}${m}${label}]")))
(labels)
)
def foldNonassocOp(numbers: Seq[Int]): Int = (
foldRight[Int, Int]
(0)
(
(n, acc) =>
if n == 0
then Eval.now(0)
else acc.map(nonassocOp(n, _))
)
(numbers)
)
*/
/** A base trait for a series of experiments using
* one particular approach to foldRight implementation.
*/
trait SolutionApproach {
/** Short description that uniquely identifies
* the approach within the context of the question.
*/
def description: String
/** Does it respect the signature requested in the question? */
def respectsSignature: Boolean = false
/** Checks whether `as` contains `e`. */
def containsElement[T](e: T)(as: Seq[T]): Boolean
/** Puts labeled brackets around a central string.
*
* E.g. `nestBrackets(List("1", "2", "3"), "<*>")) == "[1[2[3<*>3]2]1]".
*/
def nestBrackets(bracketLabels: Seq[String], center: String): String
/** A non-associative operation on integers with
* the property that `nonassocOp(0, x) = 0`.
*/
def nonassocOp(a: Int, b: Int): Int = a * s"string${b}".hashCode
/** fold-right with nonassocOp */
def foldNonassocOp(numbers: Seq[Int]): Int
/** Runs a single experiment, prints the description of the outcome */
private def runExperiment[A](label: String)(intendedOutcome: A)(body: => A): Unit = {
val resultRef = new java.util.concurrent.atomic.AtomicReference[util.Either[String, A]]()
val t = new Thread {
override def run(): Unit = {
try {
resultRef.set(util.Right(body))
} catch {
case so: StackOverflowError => resultRef.set(util.Left("StackOverflowError"))
case ni: NotImplementedError => resultRef.set(util.Left("Not implementable"))
}
}
}
val killer = new Thread {
override def run(): Unit = {
Thread.sleep(2000)
if (t.isAlive) {
// Yes, it's bad, it damages objects, blah blah blah...
t.stop()
resultRef.set(util.Left("Timed out"))
}
}
}
t.start()
killer.start()
t.join()
val result = resultRef.get()
val outcomeString =
result match
case util.Left(err) => s"[failure] ${err}"
case util.Right(r) => {
if (r == intendedOutcome) {
s"[success] ${r} (as expected)"
} else {
s"[failure] ${r} (expected ${intendedOutcome})"
}
}
val formattedOutcome = "%-40s %s".format(
s"${label}:",
outcomeString
)
println(formattedOutcome)
}
/** Runs multiple experiments. */
def runExperiments(): Unit = {
println()
println(s"----- ${description} -----")
runExperiment("does it respect the signature?")(true){ respectsSignature }
runExperiment("containsElement on infinite stream")(true){
containsElement("a")("b" #:: "b" #:: "a" #:: LazyList.continually("b"))
}
runExperiment("containsElement on 1M-long list")(true){
containsElement("a")(List.fill(1000_000)("b") ++ List("a", "b", "b"))
}
runExperiment("nested labeled brackets")("[1[2[3<*>3]2]1]"){
nestBrackets(List("1", "2", "3"), "<*>")
}
val expectedHash = (0 to 10).reverse.foldRight(0)(nonassocOp)
runExperiment("foldRight nonassocOp")(expectedHash){
foldNonassocOp((-10 to 10).toList.reverse)
}
}
}
/** Solution approch that preserves the interface in the question */
trait SignaturePreservingApproach extends SolutionApproach:
override def respectsSignature = true
/** This is the signature that was requested in the question. */
def foldRight[T, U](base: U)(f: (T, => U) => U)(as: Seq[T]): U
def containsElement[T](e: T)(as: Seq[T]): Boolean = {
foldRight(false)((el: T, acc) => if (el == e) true else acc)(as)
}
def nestBrackets(labels: Seq[String], center: String): String = {
foldRight(center)((l, w) => s"[${l}${w}${l}]")(labels)
}
def foldNonassocOp(numbers: Seq[Int]): Int = (
foldRight[Int, Int]
(0)
((n, h) => if (n == 0) 0 else nonassocOp(n, h))
(numbers)
)
@main def examples(): Unit = {
for approach <- List(
NaiveRecursive,
TailRecFromUsersScalaLangOrg,
InterThreadRecursion,
ReturnEither,
NoPostprocessing,
SyntacticallySimilarToEval,
TailRecDoneRight,
// EvalApproach, /* requires `cats` */
)
do
approach.runExperiments()
}
Requires Scala 3.
For the cats.Eval, you need a basic Cats project that can be generated with
sbt new typelevel/ce3.g8
Output for all experiments in one big table:
----- Naive recursive (from question itself, 1st attempt) -----
does it respect the signature?: [success] true (as expected)
containsElement on infinite stream: [success] true (as expected)
containsElement on 1M-long list: [failure] StackOverflowError
nested labeled brackets: [success] [1[2[3<*>3]2]1] (as expected)
foldRight nonassocOp: [success] -496880886 (as expected)
----- TailRec (from link to discussion on scala-lang.org) -----
does it respect the signature?: [success] true (as expected)
containsElement on infinite stream: [failure] Timed out
containsElement on 1M-long list: [success] true (as expected)
nested labeled brackets: [success] [1[2[3<*>3]2]1] (as expected)
foldRight nonassocOp: [success] -496880886 (as expected)
----- Inter-thread recursion -----
does it respect the signature?: [success] true (as expected)
containsElement on infinite stream: [success] true (as expected)
containsElement on 1M-long list: [success] true (as expected)
nested labeled brackets: [success] [1[2[3<*>3]2]1] (as expected)
foldRight nonassocOp: [success] -496880886 (as expected)
----- Return Either[U => U, U] -----
does it respect the signature?: [failure] false (expected true)
containsElement on infinite stream: [success] true (as expected)
containsElement on 1M-long list: [success] true (as expected)
nested labeled brackets: [success] [1[2[3<*>3]2]1] (as expected)
foldRight nonassocOp: [success] -496880886 (as expected)
----- No postprocessing -----
does it respect the signature?: [failure] false (expected true)
containsElement on infinite stream: [success] true (as expected)
containsElement on 1M-long list: [success] true (as expected)
nested labeled brackets: [failure] Not implementable
foldRight nonassocOp: [failure] Not implementable
----- Syntactically analogous to Eval -----
does it respect the signature?: [failure] false (expected true)
containsElement on infinite stream: [failure] StackOverflowError
containsElement on 1M-long list: [failure] StackOverflowError
nested labeled brackets: [success] [1[2[3<*>3]2]1] (as expected)
foldRight nonassocOp: [success] -496880886 (as expected)
----- Nice solution with Eval -----
does it respect the signature?: [failure] false (expected true)
containsElement on infinite stream: [success] true (as expected)
containsElement on 1M-long list: [success] true (as expected)
nested labeled brackets: [success] [1[2[3<*>3]2]1] (as expected)
foldRight nonassocOp: [success] -496880886 (as expected)
----- Ok solution with TailRec -----
does it respect the signature?: [failure] false (expected true)
containsElement on infinite stream: [success] true (as expected)
containsElement on 1M-long list: [success] true (as expected)
nested labeled brackets: [success] [1[2[3<*>3]2]1] (as expected)
foldRight nonassocOp: [success] -496880886 (as expected)
foldRightin Scala that meets the above criteria (in particular preserving the type signature); at least, not by using Trampolines. What is your feeling on this? – LatashalatashiafoldRight, it requires materialisation of not only the infinite data structure but also the trampolined computation stack (which will require few times more memory than the data itself). – Schottische