FoldRight over Infinite Structures in Scala using Trampolines-CodePudding

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?

CodePudding user response：

It can't be done