FoldRight over Infinite Structures in Scala using Trampolines

Question

FoldRight over Infinite Structures in Scala using Trampolines

383 Views Asked by Hugo Sereno Ferreira At 31 October 2022 at 14:39

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?

Original Q&A

There are 2 best solutions below

Andrey Tyukin On 06 November 2022 at 13:16

An Addendum: Throwing Exceptions

(the main answer got over the character limit, continuing here)

I eventually came up with a particularly bizarre implementation that manages to run on a single thread, but also seems to completely dissolve temporal order, causality, and sanity.

It is based on exception-throwing and re-running parts of the computation.

This solution has the following strange properties:

(a) It preserves the original function signature
(b) It works on infinite streams
(c) It works on very long lists
(!d) It must keep an auxiliary list of Ts
(t) It works with one single thread!
(-) It sometimes does twice as much work as necessary, and for non-pure functions f, one can detect that it's reordering the decisions in a strange way.

Here it is:

  def foldRight[T, U](base: U)(f: (T, => U) => U)(as: Seq[T]): U = {
    def tryToFinish(t: T): Option[U] = {
      try {
        Some(f(t, throw new RuntimeException))
      } catch {
        case _: RuntimeException => None
      }
    }
    @annotation.tailrec
    def rec(reversedHeads: List[T], rest: Seq[T]): U = {
      rest match
        case head +: tail => tryToFinish(head) match
          case Some(done) => reversedHeads.foldLeft(done)((acc, h) => f(h, acc))
          case None => rec(head :: reversedHeads, tail)
        case _ => reversedHeads.foldLeft(base)((acc, h) => f(h, acc))
    }
    rec(Nil, as)
  }

For pure functions f, it might even seem to work. In order to detect that it doesn't work quite as one would expect from a foldRight, one has to pass an f that has side-effects, e.g. that prints a log-message each time it makes a decision whether to continue or not.

For example, if f is searching for 0 in the list [2, 1, 0, -1], a "normal" implementation of foldRight would produce the following sequence of decisions:

  2 -> continue
  1 -> continue
  0 -> done

The above implementation, however, performs the following actions:

  2 -> continue
  1 -> continue
  0 -> done
  1 -> continue
  2 -> continue

i.e. some of the decisions are repeated in the reverse order.

Updated Full Code

/** This is the very first solution proposed in the question itself.
  *
  * It's also seems to be wide-spread among multiple other blogs
  * and articles.
  *
  * The problem with it is that it cannot deal with situations where
  * it has to consider millions of elements before coming up with a
  * solution.
  */
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) from the question, 
  * 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 change in the signature, 
  * and also creates long lists of closures, 
  * sometimes unnecessarily. 
  */
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)
  )

  def sideEffectsLog(numbers: Seq[Int]): String = {
    var log = List.empty[String]
    (foldRight
      (0)
      (
        (n: Int) => 
          if n == 0 
          then
            log :+= s"${n}->done"
            Right(0) 
          else
            log :+= s"${n}->cont"
            Left((h: Int) => nonassocOp(n, h))
      )
      (numbers)
    )
    log.mkString(";")
  }


/** If we restrict the signature so that the `f` can
  * only peek at the heads, but never receives any
  * information coming from the tail, we obtain something
  * that behaves more like a "collect first" instead of a
  * "foldRight". It's sufficient for `containsElement`,
  * but insufficient for other methods.
  */
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 = ???
  def sideEffectsLog(numbers: Seq[Int]): String = ???


/** 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)
  )
 
  def sideEffectsLog(numbers: Seq[Int]): String = {
    var log = List.empty[String]
    (foldRight[Int, Int]
      (0)
      (
        (n, acc) =>
          if n == 0 
          then
            log :+= s"${n}->done"
            0
          else
            log :+= s"${n}->cont"
            nonassocOp(n, acc)
      )
      (numbers)
    )
    log.mkString(";")
  }
 


/** A `TailRec`-based solution that
  *   - works for infinite streams
  *   - works with very long lists
  *   - uses single thread
  *   - does not create unnecessarily long lists of closures in the memory
  */
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)
  )

  def sideEffectsLog(numbers: Seq[Int]): String = {
    var log = List.empty[String]
    (foldRight[Int, Int]
      (0)
      (
        (n, acc) =>
          if n == 0 
          then
            log :+= s"${n}->done"
            done(0) 
          else 
            log :+= s"${n}->cont"
            acc.map(nonassocOp(n, _))
      )
      (numbers)
    )
    log.mkString(";")
  }



/** Bonus: same as "TailRec Done Right", but with `cats.Eval` */
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)
  )

  def sideEffectsLog(numbers: Seq[Int]): String = {
    var log = List.empty[String]
    (foldRight[Int, Int]
      (0)
      (
        (n, acc) =>
          if n == 0 
          then
            log :+= s"${n}->done"
            Eval.now(0) 
          else 
            log :+= s"${n}->cont"
            acc.map(nonassocOp(n, _))
      )
      (numbers)
    )
    log.mkString(";")
  }


/** The solution that satisfies all properties (a), (b), (c) from the question, 
  * but relies on exceptions and repeated evaluation of `f`s.
  */
object Rollback extends SignaturePreservingApproach:
  def description = "Rollback"

  def foldRight[T, U](base: U)(f: (T, => U) => U)(as: Seq[T]): U = {
    def tryToFinish(t: T): Option[U] = {
      try {
        Some(f(t, throw new RuntimeException))
      } catch {
        case _: RuntimeException => None
      }
    }
    @annotation.tailrec
    def rec(reversedHeads: List[T], rest: Seq[T]): U = {
      rest match
        case head +: tail => tryToFinish(head) match
          case Some(done) => reversedHeads.foldLeft(done)((acc, h) => f(h, acc))
          case None => rec(head :: reversedHeads, tail)
        case _ => reversedHeads.foldLeft(base)((acc, h) => f(h, acc))
    }
    rec(Nil, as)
  }


/** 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

  /** Same as foldNonassocOp, but instead of the `Int`-result, 
    * returns a semicolon-separated list of decisions made during the
    * evaluation.
    *
    * See how this method is used in the actual test to understand the expected format.
    */
  def sideEffectsLog(numbers: Seq[Int]): String 


  /** 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)
    }
    runExperiment("Order of side effects")("2->cont;1->cont;0->done") {
      sideEffectsLog(List(2, 1, 0, -1))
    }
  }
}


/** 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)
  )

  def sideEffectsLog(numbers: Seq[Int]): String = {
    var log = List.empty[String]
    (foldRight[Int, Int]
      (0)
      ((n, h) => 
        if n == 0
        then
          log :+= s"${n}->done"
          0
        else
          log :+= s"${n}->cont"
          nonassocOp(n, h)
      )
      (numbers)
    )
    log.mkString(";")
  }


@main def examples(): Unit = {
  for approach <- List(
    NaiveRecursive,
    TailRecFromUsersScalaLangOrg,
    InterThreadRecursion,
    ReturnEither,
    NoPostprocessing,
    SyntacticallySimilarToEval,
    TailRecDoneRight,
    EvalApproach, /* requires `cats` */
    Rollback,
  )
  do
    approach.runExperiments()
}

Table that also includes the experiment about the order of side-effects:

----- 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)
Order of side effects:                   [success] 2->cont;1->cont;0->done (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)
Order of side effects:                   [failure] -1->cont;0->done;1->cont;2->cont (expected 2->cont;1->cont;0->done)

----- 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)
Order of side effects:                   [success] 2->cont;1->cont;0->done (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)
Order of side effects:                   [success] 2->cont;1->cont;0->done (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
Order of side effects:                   [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)
Order of side effects:                   [failure] -1->cont;0->done;1->cont;2->cont (expected 2->cont;1->cont;0->done)

----- 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)
Order of side effects:                   [success] 2->cont;1->cont;0->done (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)
Order of side effects:                   [success] 2->cont;1->cont;0->done (as expected)

----- Rollback -----
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)
Order of side effects:                   [failure] 2->cont;1->cont;0->done;1->cont;2->cont (expected 2->cont;1->cont;0->done)

PPS: The updated code also shows that the broken TailRec implementation from the linked scala-lang.org discussion performs all decisions in the reverse order, and ignores all outcomes.

**Andrey Tyukin** · Accepted Answer · 2022-11-04T02:07:15.610000

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)

FoldRight over Infinite Structures in Scala using Trampolines

There are 2 best solutions below

TL;DR

Overview

Naive Recursion

Failed `TailRec`

Inter-Thread Recursion

No Frameworks: Returning `Either[U => U, U]`

No Postprocessing

Back to `TailRec`: `TailRec` Done Right

Full code

An Addendum: Throwing Exceptions

Updated Full Code

Related Questions in SCALA

Related Questions in FOLD

Related Questions in TAIL-CALL-OPTIMIZATION

Related Questions in TRAMPOLINES

Trending Questions

Popular # Hahtags

Popular Questions

FoldRight over Infinite Structures in Scala using Trampolines

There are 2 best solutions below

TL;DR

Overview

Naive Recursion

Failed TailRec

Inter-Thread Recursion

No Frameworks: Returning Either[U => U, U]

No Postprocessing

Back to TailRec: TailRec Done Right

Full code

An Addendum: Throwing Exceptions

Updated Full Code

Related Questions in SCALA

Related Questions in FOLD

Related Questions in TAIL-CALL-OPTIMIZATION

Related Questions in TRAMPOLINES

Trending Questions

Popular # Hahtags

Popular Questions

Failed `TailRec`

No Frameworks: Returning `Either[U => U, U]`

Back to `TailRec`: `TailRec` Done Right