concept foldLeft in category functional programming

This is an excerpt from Manning's book Grokking Functional Programming MEAP V11. Login to get full access to this book.

4.53   Reducing many values into one value using foldLeft

You’ve already seen how quickly were we able to implement all the requirements so far. We used List’s sortBy, map & filter—functions that take other functions as parameters, use them internally and return a new immutable value back. Yes, this new requirement can also be implemented using the same technique. The function we introduce here is called foldLeft. Here’s one possible implementation of the new requirement using Scala and its built-in immutable List that has a foldLeft function:

def cumulativeScore(wordScore: String => Int,
                    words: List[String]): Int = {
  words.foldLeft(0)((total, word) => total + wordScore(word))
}

copy

Yes, foldLeft is a little bit different than the previous ones, but the general rule stays the same. What it does is it takes each element of the list, applies the provided function to it and an ongoing total, and then passes it to the next element. Again, it doesn’t mutate anything.

The body of the function consists of just the call to foldLeft, which takes an Int and a function that takes two parameters and returns an Int.

This is an excerpt from Manning's book Functional Programming in Java: How functional techniques improve your Java programs. Login to get full access to this book.

But wait. Addition is a commutative operation. If you use a noncommutative operation, you must change the operation as well. If you don’t, you could end up with two different situations, depending on the types. If the operation has operands of different types, if won’t compile. On the other hand, if the operation has operands of the same types but it isn’t commutative, you’ll get a wrong result with no error. So foldLeft and foldRight have the following relationship, where operation1 and operation2 give the same results with the same operands in reverse order:

Instead of using foldRight, create a foldLeft method that’s tail recursive and can be made stack-safe. Here’s its signature:

Note that you can also define foldLeft in terms of foldRight, although this is much less useful:

public static <A, B> B foldLeftViaFoldRight(List<A> list,
                              B identity, Function<B, Function<A, B>> f) {
  return List.foldRight(list.reverse(),identity, x -> y ->
                                                    f.apply(y).apply(x));
}

copy

Again, note that the foldLeft method you use is an instance method of List. In contrast, foldRight is a static method. (We’ll define an instance foldRight method soon.)