3.10

Our implementation of foldRight is not tail-recursive and will result in a StackOverflowError for large lists (we say it’s not stack-safe). Convince yourself that this is the case, and then write another general list-recursion function, foldLeft, that is tail-recursive, using the techniques we discussed in the previous chapter. Here is its signature

def foldLeft[A,B](as: List[A], z: B)(f: (B, A) => B): B

Solution

def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B = l match {
  case Nil => z
  case Cons(head, tail) => foldLeft(tail, f(z, head))(f)
}

Run

object Solution extends App {
  import List._

  println("foldLeft Sum List(1,2,3): " + foldLeft(List(1,2,3), 0)(_+_))
  println("foldLeft Product List(1,2,3): " + foldLeft(List(1,2,3), 1)(_*_))
}

Output

foldLeft Sum List(1,2,3): 6
foldLeft Product List(1,2,3): 6