Exploring Scala foldLeft and foldRight

Scala collections let you "fold" the data in the collection into a single result. In the Scaladoc, it says that it "Folds the elements of this traversable or iterator using the specified associative binary operator."

Let's play with this concept. Since fold() is the most flexible and powerful, let's warm up by looking at the simpler foldLeft and foldRight methods.

These fold* operations will apply to a collection, so let's create a simple one:
scala> val a = List(1,2,3)
a: List[Int] = List(1, 2, 3)
scala> a.foldLeft(7)(_+_)
res1: Int = 13

What just happened? We created a List of integers, and called foldLeft on the List. We provided two parameters. The first is the start value, in this case 7. The second is a binary operation, in this case an addition.

Since foldLeft applies the binary operation to the start value and each of the elements in the collection, going left to right, the steps to the result are:
7 + 1 = 8
8 + 2 = 10
10 + 3 = 13


Since addition of integers is a commutative property, the order of the operands does not change the result; A + B equals B + A. So since foldRight applies the binary operator right to left, we would expect the same result if we called foldRight:\
scala> a.foldRight(7)(_+_)
res2: Int = 13

Scala also provides some syntactic sugar to save typing, the "/:" and ":\" operators. At first glance, these are potentially confusing to read and use. A handy memory trick is to see them as moving toward the colon. So, "/:" has the slash on the left and colon on the right, it moves left to right, it must be foldLeft. On the other hand, ":\" has the slash on the right and colon on the left, moving right to left means it's foldRight. And my memory trick for whether to use forward or back-slash is that the upper part should be over (or nearest) the colon. So ":\" needs the back-slash and "/:" uses the forward-slash.
scala> (7 /: a)(_+_)
res3: Int = 13

scala> (a :\ 7)(_+_)
res4: Int = 13

Those look identical, since addition is commutative. Let's use a binary operator that is not commutative and see the difference between foldLeft and foldRight. For example, minus: 7 - 4 != 4 - 7
scala> a.foldLeft(7)(_-_)
res5: Int = 1

Where did the 1 come from? The start value starts on the left, and the result carries over to the left of the subsequent calculations, so we calculate 7 - 1 = 6; 6 - 2 = 4; 4 - 3 = 1

Likewise:
scala> a.foldRight(7)(_-_)
res6: Int = -5

That might at first catch you by surprise. Since the start value is 7 and there are only 6 (1+2+3) values to subtract, how do we get -5? Remember that, for foldRight, the start value is to the RIGHT of the operand. So the calculations are, from rightmost item in the collection to leftmost: 3 - 7 = -4; 2 - -4 = 6; 1 - 6 = -5

Since this might be counter-intuitive at first, let's do a second example:
scala> a.foldRight(2)(_-_)
res7: Int = 0

The first calculation in the sequence is: 3 (the rightmost Int) minus (the binary operator) 2 (the start value) = 1; then 2 (the next Int in the List) minus 1 (the carried-over start value) = 1; then 1 (the leftmost Int) minus 1 (the carried-over start value) = 0

Instead of Ints, let's switch to a List of single characters:
scala> val c = List("t", "o", "p")
c: List[String] = List(t, o, p)

Now, do a foldLeft with Strings, using "s" as the start value. The binary + operator concatenates Strings, so we get:
scala> ("s" /: c)(_+_)
res8: String = stop

Doing a foldRight with Strings shows more clearly maybe than the Integer examples, that the start value goes to the right of the binary operator.
scala> (c :\ "s")(_+_)
res21: String = tops

I will dig into the more flexible fold another day.