Skip to main content

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.


Labels:

Popular posts from this blog

How to do Git Rebase in Eclipse

This is an abbreviated version of a fuller post about Git Rebase in Eclipse. See the longer one here : One side-effect of merging Git branches is that it leaves a Merge commit. This can create a history view something like: The clutter of parallel lines shows the life spans of those local branches, and extra commits (nine in the above screen-shot, marked by the green arrows icon). Check out this extreme-case history:  http://agentdero.cachefly.net/unethicalblogger.com/images/branch_madness.jpeg Merge Commits show all the gory details of how the code base evolved. For some teams, that’s what they want or need, all the time. Others may find it unnecessarily long and cluttered. They prefer the history to tell the bigger story, and not dwell on tiny details like every trivial Merge-commit. Git Rebase offers us 2 benefits over Git Merge: First, Rebase allows us to clean up a set of local commits before pushing them to the shared, central repository. For this
Read more

Java 8: Rewrite For-loops using Stream API

Java 8 Tip: Anytime you write a Java For-loop, ask yourself if you can rewrite it with the Streams API. Now that I have moved to Java 8 in my work and home development, whenever I want to use a For-loop, I write it and then see if I can rewrite it using the Stream API. For example: I have an object called myThing, some Collection-like data structure which contains an arbitrary number of Fields. Something has happened, and I want to set all of the fields to some common state, in my case "Hidden"
Read more

Git Reset in Eclipse

Using Git and the Eclipse IDE, you have a series of commits in your branch history, but need to back up to an earlier version. The Git Reset feature is a powerful tool with just a whiff of danger, and is accessible with just a couple clicks in Eclipse. In Eclipse, switch to the History view. In my example it shows a series of 3 changes, 3 separate committed versions of the Person file. After commit 6d5ef3e, the HEAD (shown), Index, and Working Directory all have the same version, Person 3.0.
Read more

Code Coverage in C#.NET Unit Tests - Setting up OpenCover

The purpose of this post is to be a brain-dump for how we set up and used OpenCover and ReportGenerator command-line tools for code coverage analysis and reporting in our projects. The documentation made some assumptions that took some digging to fully understand, so to save my (and maybe others') time and effort in the future, here are my notes. Our project, which I will call CEP for short, includes a handful of sub-projects within the same solution. They are a mix of Web APIs, ASP MVC applications and Class libraries. For Unit Tests, we chose to write them using the MSTest framework, along with the Moq mocking framework. As the various sub-projects evolved, we needed to know more about the coverage of our automated tests. What classes, methods and instructions had tests exercising them, and what ones did not? Code Coverage tools are conveniently built-in for Visual Studio 2017 Enterprise Edition, but not for our Professional Edition installations. Much less for any Commun
Read more

Scala Collections: A Group of groupBy() Examples

Scala provides a rich Collections API. Let's look at the useful groupBy() function. What does groupBy() do? It takes a collection, assesses each item in that collection against a discriminator function, and returns a Map data structure. Each key in the returned map is a distinct result of the discriminator function, and the key's corresponding value is another collection which contains all elements of the original one that evaluate the same way against the discriminator function. So, for example, here is a collection of Strings: val sports = Seq ("baseball", "ice hockey", "football", "basketball", "110m hurdles", "field hockey") Running it through the Scala interpreter produces this output showing our value's definition: sports: Seq[String] = List(baseball, ice hockey, football, basketball, 110m hurdles, field hockey) We can group those sports names by, say, their first letter. To do so, we need a disc
Read more