Warning for recursive functions without tailrec annotation

speaking of students, as a potential point of interest, when they learn about left fold and right fold they are told that while the first one is tail-recursive

π‘“π‘œπ‘™π‘‘π‘™ ∷ (𝛽 β†’ 𝛼 β†’ 𝛽) β†’ 𝛽 β†’ [𝛼] β†’ 𝛽
π‘“π‘œπ‘™π‘‘π‘™ 𝑓 𝑒 [] = 𝑒
π‘“π‘œπ‘™π‘‘π‘™ 𝑓 𝑒 (π‘₯:π‘₯𝑠) = π‘“π‘œπ‘™π‘‘π‘™ 𝑓 (𝑓 𝑒 π‘₯) π‘₯𝑠
𝑖.𝑒. π‘“π‘œπ‘™π‘‘π‘™ (βŠ•) 𝑒 [π‘₯1,π‘₯2,π‘₯3] = ((𝑒 βŠ• π‘₯1) βŠ• π‘₯2) βŠ• π‘₯3

@tailrec def foldl[A,B](f: B => A => B)(e: B)(s: List[A]): B = s match {
  case Nil   => e
  case x::xs => foldl(f)(f(e)(x))(xs)
}

the second is not, and so is susceptible to stack overflow errors

π‘“π‘œπ‘™π‘‘π‘Ÿ ∷ (𝛼 β†’ 𝛽 β†’ 𝛽) β†’ 𝛽 β†’ [𝛼] β†’ 𝛽
π‘“π‘œπ‘™π‘‘π‘Ÿ 𝑓 𝑒 [] = 𝑒
π‘“π‘œπ‘™π‘‘π‘Ÿ 𝑓 𝑒 (π‘₯:π‘₯𝑠) = 𝑓 π‘₯ (π‘“π‘œπ‘™π‘‘π‘Ÿ 𝑓 𝑒 π‘₯𝑠)
𝑖.𝑒. π‘“π‘œπ‘™π‘‘π‘Ÿ (βŠ•) 𝑒 [π‘₯1,π‘₯2,π‘₯3] = π‘₯1 βŠ• (π‘₯2 βŠ• (π‘₯3 βŠ• 𝑒))

def foldr[A,B](f: A => B => B)(v: B)(s: List[A]): B = s match {
  case Nil   => v
  case x::xs => f(x)(foldr(f)(v)(xs))
}

When they go and check out foldRight for Lists in Scala though, they find out that it is not recursive at all:

final override def foldRight[B](z: B)(op: (A, B) => B): B = {
var acc = z
var these: List[A] = reverse
while (!these.isEmpty) {
  acc = op(these.head, acc)
  these = these.tail
}
acc

}

The foldRight implementation in IterableOnce is even more evidently defined in terms of foldLeft:

def foldRight[B](z: B)(op: (A, B) => B): B = reversed.foldLeft(z)((b, a) => op(a, b))

Another surprise is in store when they look at the Foldable[List] implementation of foldRight in Cats, which uses recursion but not tail-recursion, and which avoids the stack overflow problem by using the Eval monad, which provides trampolining:

  def foldRight[A, B](fa: List[A], lb: Eval[B])(f: (A, Eval[B]) => Eval[B]): Eval[B] = {
    def loop(as: List[A]): Eval[B] =
      as match {
        case Nil    => lb
        case h :: t => f(h, Eval.defer(loop(t)))
      }
    Eval.defer(loop(fa))
  } 

As the β€˜Scala with Cats’ book says: "One useful property of Eval is that its map and flatMap methods are trampolined. This means we can nest calls to map and flatMap arbitrarily without consuming stack frames. We call this property β€œstack safety”.

1 Like