Let's start with a straightforward definition of foldRight:
def foldRight[T, U](base: U)(f: (T, => U) => U)(as: Seq[T]): U = {
as match {
case Nil => base
case head +: next => f(head, foldRight(base)(f)(next))
}
}
One of the advantages of such combinator is that it allows us to write something like (I use an if to make the short-circuiting behaviour of || more explicit):
def containsElement[T](e: T)(as: Seq[T]): Boolean = {
foldRight(false)((el: T, acc) => if (el == e) true else acc)(as)
}
Which then works with infinite structures:
val bs = 0 #:: 1 #:: 2 #:: 3 #:: LazyList.continually(1)
containsElement(3)(bs)
However, it doesn't work with very looooong sequences, because we are blowing up the stack:
val veryLongList = List.fill(1_000_000)(0) :+ 3
containsElement(3)(veryLongList)
... would result in a java.lang.StackOverflowError.
Enter the scala.util.control.TailCalls. We can write a very specialised implementation of containsElement that takes advantage of TCO, such as:
def containsElement[T](e: T)(as: Seq[T]) = {
import scala.util.control.TailCalls._
def _rec(as: Seq[T]): TailRec[Boolean] = {
as match {
case Nil => done(false)
case head +: next => if (head == e) done(true) else _rec(next)
}
}
_rec(as).result
}
But now I want to generalize this to foldRight. The following code was as far as I got via incremental refactoring, but if I keep following this path, I will bump into the fact that I would need to change the f signature to f: (T, => TailRec[U]) => U which is not what I wanted at all:
def containsElement[T](e: T)(as: Seq[T]) = {
import scala.util.control.TailCalls._
val base = false
def f(head: T, next: => TailRec[Boolean]): TailRec[Boolean] = if (head == e) done(true) else next
def _rec(as: Seq[T]): TailRec[Boolean] = {
as match {
case Nil => done(base)
case head +: next => f(head, _rec(next))
}
}
_rec(as).result
}
Question: how can we create an implementation of foldRight that (a) preserves the [T, U](base: U)(f: (T, => U) => U)(as: Seq[T]): U signature, (b) works on infinite structures, and (c) doesn't blow up with a StackOverflowError in very long structures?
It can't be done 🙂 (at least not on a single JVM thread with limited stack).
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
f cannot return until all the subsequent invocations of f have returned;f must be able to hold some data in its stack frame from the beginning to the end;f that coexist simultaneouslyNo 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.
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:
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 "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:
TailRec can be replaced by cats.Eval. 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:
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.
TailRecIn 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
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").
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
x;u, invoking f for the second, third, fourth... millionth time.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).
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)).
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).
TailRec: TailRec Done RightHaving 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).
/** 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)