Stack safety

Stack safety is the ability to process inputs whose size grows without exhausting the call stack. Recursive code is not automatically stack-safe: when a call must still construct or combine a result after its recursive call returns, each input element can leave pending work on the stack. The central question is therefore operational: does each step finish its work before making the next call, or is the remaining work represented another way? section 3.6 section 5.6

For strict lists, tail recursion gives a direct answer. Carry the partial result in an accumulator, update it for the current element, and recur on the tail. Since the recursive call is the final action, no stack frame must wait for it. A tail-recursion annotation asks the compiler to verify that this property holds rather than leaving it as an assumption. section 3.6

@annotation.tailrec
def foldLeft[A, B](as: List[A], acc: B, f: (B, A) => B): B =
  as match
    case Nil => acc
    case Cons(hd, tl) => foldLeft(tl, f(acc, hd), f)

A tail-recursive fold consumes one list cell at a time while passing the updated accumulator into the next call; the recursive call has no work after it. section 3.6

A right fold highlights the trade-off. Its usual traversal needs the result from the tail before it can combine the current head, so a simple stack-safe version first reverses the list and then uses foldLeft with flipped arguments. This makes two passes. Alternatively, foldLeft can accumulate a function from B to B, beginning with the identity function; applying that composed function to the initial value produces the right-fold result. section 3.6 section 3.6

Stack safety can arise through distinct designs:

• Use an accumulator and tail recursion when processing can advance while retaining only the current state. section 3.6
• Reverse a strict list before a left fold when right-fold ordering is required and an extra traversal is acceptable. section 3.6
• Accumulate an endomorphism, B => B, when converting between left and right folds without directly accumulating a B. section 3.6
• Suspend recursive work in a lazy tail when building a lazy result, so recursion occurs only when that tail is forced. section 5.6
• Use trampolining for stack-safe monadic composition when computations are represented as values and interpreted separately. section 13.10

Laziness changes how recursive position should be read. LazyList.take appears to recurse while constructing a Cons, which would be unsafe for an eager structure. Here the call is stored in the returned tail and runs only when that tail is demanded, so it does not build an eager chain of pending calls. By contrast, converting a LazyList to a strict List needs an explicitly tail-recursive loop and accumulator. section 5.6 section 5.6

def take(n: Int): LazyList[A] = this match
  case Cons(h, t) if n > 1 => cons(h(), t().take(n - 1))
  case Cons(h, t) if n == 1 => cons(h(), empty)
  case _ => empty

The recursive take call is placed inside the lazy tail of cons; requesting one element has a separate case that avoids forcing an unused tail. section 5.6

The same concern extends beyond data-structure traversal. An initial IO representation can preserve computations as ordinary values yet still fail on deeply composed programs. Trampolining supplies stack-safe function composition through TailRec; Async applies a similar approach to Par values, and Free generalizes the sequencing of primitive algebra operations before interpretation. section 13.10 section 13.10