Collection/Iterable/Iterator foldRight and foldLeft

Folding and reducing are two types of operations that are both very important with dealing with collections in Scala (and other functional languages). This topic covers the fold operations. The reduce topic was previously covered.

A simplistic explanation is they allow processing of the collections. I think about foldRight and foldLeft to be very similar to a visitor that visits each element and performs a calculation. It does not change the values of the collection instead it calculates a result from visiting each element. In Java you might see the following pattern:

1. class Collection {
2.   pubic Result op( Result startingValue, Op operation){...}
3. }
5. interface Op{
6.   public Result op( Object nextCollectionElem, Result lastCalculatedResult)
7. }

To a Java programmer this is pretty obvious how you use it. This is essentially the fold operation. The difference is we are using closures so there is almost no boilerplate and all collection/Iteratore/Iterable interfaces have the fold methods.

One last point before examples. For fold and reduce operations there are both foldLeft and foldRight and similarly reduceLeft and reduceRight. These indicate the order that a collection is processed. Note that for certain collections one direction is more performant that the other. Lists, for example, are better to process left to right because of the datastructure used.

Some tasks that are suited to fold are:

• Find the 5 smallest elements in a list
• Sum all the values of a Map together
• Sum the lengths of the Strings contained in the collection

There are a number of ways that fold can be written syntactically. The following examples are ways to sum together the integers of a Map. Note that /: is an alias for foldLeft and :/ is an alias for foldRight. Normally foldLeft and foldRight should be used unless the rest of the developers who will be reading the code are quite confortable reading Scala.

1. // fold right processes from left to right
2. scala> val m = Map(1 -> "one", 2 -> "two", 3 -> "three")
3. m: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> one, 2 -> two, 3 -> three)
5. scala> m.foldRight(0)((kv: (Int, String), a : Int) => a+kv._2.length)
6. res1: Int = 11
8. scala> (m :\ 0)((kv: (Int, String), a : Int) => a+kv._2.length)
9. res5: Int = 11
11. scala> m.foldRight(0){ case ((key, value), a) => a+value.length}
12. res7: Int = 11
14. scala> m.foldRight(0){ case (kv, a) => a+kv._2.length} }}
15. res8: Int = 11
17. // fold left processes from right to left (usually slower than foldRight)
18. scala> val m = Map("a" -> 1, "b" -> 2, "c" -> 3)
19. m: scala.collection.immutable.Map[java.lang.String,Int] = Map(a -> 1, b -> 2, c -> 3)
21. scala> m.foldLeft(0)( (accum, kv) => accum + kv._2 )
22. res9: Int = 6
24. scala> m.foldLeft(0){case (accum, (key, value)) => accum + value}
25. res5: Int = 6
27. scala> (0 /: m){case (accum, (key, value)) => accum + value}
28. res4: Int = 6