Scala Code Review: foldLeft and foldRight | Matt Malone's Old-Fashioned Software Development Blog

Scala Code Review: foldLeft and foldRight | Matt Malone's Old-Fashioned Software Development Blog
Scala Code Review: foldLeft and foldRight One of my favorite functional programming tricks is folding. The fold left and fold right functions can do a lot of complicated things with a small amount of code. Today, I'd like to (1) introduce folding, (2) make note of some surprising, nay, shocking fold behavior, (3) review the folding code used in Scala's List class, and (4) make some presumptuous suggestions on how to improve List. Update: I've created a new post in which I list lots and lots of foldLeft examples in case you'd like to learn more about what folding can accomplish.

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

The first parameter, z, is of type B, which is to say it can be different from the list contents type. The second parameter, f, is a function that takes a B and an A (a list item) as parameters, and it returns a value of type B. So the purpose of function f is to take a value of type B, use a list item to modify that value and return it.

The foldLeft function goes through the whole List, from head to tail, and passes each value to f. For the first list item, that first parameter, z, is used as the first parameter to f. For the second list item, the result of the first call to f is used as the B type parameter.

For example, say we had a list of Ints 1, 2, and 3. We could call foldLeft(“X”)((b,a) => b + a). For the first item, 1, the function we define would add string “X” to Int 1, returning string “X1″. For the second list item, 2, the function would add string “X1″ to Int 2, returning “X12″. And for the final list item, 3, the function would add “X12″ to 3 and return “X123″.

list.foldLeft(List[Int]())((b,a) => a :: b)

override def foldLeft[B](z: B)(f: (B, A) => B): B = {

  var acc = z

  var these = this

  while (!these.isEmpty) {

    acc = f(acc, these.head)

    these = these.tail

  }

  acc

}

 

override def foldRight[B](z: B)(f: (A, B) => B): B = this match {

  case Nil => z

  case x :: xs => f(x, xs.foldRight(z)(f))

}

list.foldRight("X")((a,b) => a + b)

list.reverse.foldLeft("X")((b,a) => a + b)

def foldRight[B](z: B)(f: (A, B) => B): B =

  reverse.foldLeft(z)((b,a) => f(a,b))

 

def foldRight[B](z: B)(f: (A, B) => B): B =

  if (length > 50) reverse.foldLeft(z)((b,a) => f(a,b))

  else             originalFoldRight(z)(f)

 

def foldRight[B](z: B)(f: (A, B) => B): B =

  try {

    originalFoldRight(z)(f)

  } catch {

    case e1: StackOverflowError => reverse.foldLeft(z)((b,a) => f(a,b))

  }

Read full article from Scala Code Review: foldLeft and foldRight | Matt Malone's Old-Fashioned Software Development Blog