Category Archives: Uncategorized

Simply Scala – foldLeft & foldRight

This requires some basic knowledge about Scala. This time I’ll try to explain a bit about foldLeft and foldRight. These functions are meant to derive a result out of a collection of values. As a start I will give three examples in Java:

  • Summing all the values inside a collection of numbers.
    	int sumIntegers(List list) {
    	  int accumulator = 0;
    	  for (int item: list) {
    	    accumulator = accumulator + item;
    	  }
    	  return accumulator;
    	}
    	
  • Multiplying all the values inside a collection of numbers.
            int productIntegers(List list) {
              int accumulator = 1;
              for (int item: list) {
                accumulator = accumulator * item;
              }
              return accumulator;
            }
            
  • Finding the shortest string inside a collection of strings.
    	// For the sake of simplicity we are assuming that there are no 'null' contents in the list.
    	String findShortestString(List list) {
    	  String accumulator = list.get(0);
    	  for (String item: list) {
    	    accumulator = item.length() < accumulator.length() ? item : accumulator;
    	  }
    	  return accumulator;
    	}
    	

They look very much alike, don’t you think?

Such scenarios of deriving some value out of a collection of values are not unusual. Hence the solutions are also very similar. They are different mainly in two things: The initial accumulator value and How the accumulator is calculated as it is compared to every item. If only we could generalise the three functions above into a generic function where we could pass those 2 things, the code will be much simpler. More or less it will look like this code below. Please note that this code won’t compile since in Java (< version 8) we cannot pass function as a parameter. I’m just trying to convey my point here.

<T> T deriveSomethingOutOfThisList(List list, T accumulator, Function f) {
  for (T item: list) {
    accumulator = f(accumulator, item)
  }
  return accumulator;
}

How do we implement these functions in Scala?

In Scala a built-in feature has been provided to cater for such scenarios, which is by using either foldLeft or foldRight. This is how those three functions are defined in Scala

  // For the sake of simplicity we are assuming that there are no 'null' contents in the list.

  // Initial accumulator value = 0. 
  // The accumulator is recalculated with an addition in every iteration.
  val sumIntegers = list.foldLeft(0)((accumulator, item) => accumulator + item)

  // Initial accumulator value = 1.
  // The accumulator is recalculated with a multiplication in every iteration.
  val productIntegers = list.foldLeft(1)((accumulator, item) => accumulator * item)

  // Initial accumulator value = the first item in the list.
  // The accumulator is compared and updated if the iterated item is shorter.
  val shortestString = list.foldLeft(list(0))((accumulator, item) => {
                         if (item.length<accumulator.length) item
                         else accumulator
                       })

I’m discussing the 1st one. Once you understand how it works for the 1st one, it should be easy enough to understand the other two. Take a look at this line:

  val sumIntegers = list.foldLeft(0)((accumulator, item) => accumulator + item)

Method foldLeft belongs to the collection instance. It takes two parameters:

  • The initial accumulator value, which is 0, and
  • The function to recalculate the accumulator.This function takes two parameters: The accumulator and the list item. In this case we want the accumulator to be the sum of every list item. Hence the addition.

The other two examples follow the same behaviour as the first one. I’m leaving them to you to play around with the values and give it a try.

BTW, the naming is not very strict in the function definition above. I’m just naming them accumulator and item for the sake of readability. If you want, you can name them differently as shown below:

  val sumIntegers = list.foldLeft(0)((a, b) => a + b)

Wait, where is foldRight?

In all the examples stated above we always use foldLeft. What about foldRight? What’s the difference between them? Why am I not using foldRight at all in these examples?

There are a few differences between them:

  • Method foldLeft will trace the list item from the left to the right. While foldRight, right to the left. Shown below:
    • foldLeft: ((((1 + 2) + 3) + 4) + 5)
    • foldRight: (1 + (2 + (3 + (4 + 5))
  • Method foldRightmay throw StackOverflowException if there are too many items in the list. It’s not the case for foldLeft. More detailed explanations below.

Method foldLeft‘s implementation uses the while...do in order to trace every list item while method foldRight will trace every list item recursively. There is a drawback by looping the list recursively: it consumes more memory. Stack memory to be more exact. If the list contains too many items, the system is more likely to throw StackOverflowException. That’s why in most cases foldLeft is always preferred to foldRight.

But why are they different?

The answer lies in the way a List is structured in Scala. Scala’s List is different than Java’s. I’d just briefly say that when Scala defines a list such as List(1, 2, 3), in the back-end it’s actually structured as List(1, List(2, List(3, Nil))). Yes, by its very nature List is nested in Scala. Pretty strange, huh?

This demands another article for more thorough explanation. I have no plan to cover this in the future. I’m sure other people can explain it better than I do.

So basically foldRight is useless?

Yes. Most of the time. I have not yet found a scenario where it is better to use foldRight rather than foldLeft. And I don’t think this behaviour will change in the near future. It’s just the way it is natively structured in Scala.

And now, the not-so-sweetener syntactic sugars.

There is a syntactic sugar for method foldLeft and foldRight. Personally, I don’t like it because the way it’s used is not very common and confusing. Anyway, you can define the sumIntegers method above by using either foldLeft and foldRight like this:

  • foldLeft:
        val sumIntegers = (0 /: list)((accumulator, item) => accumulator + item)
        
  • foldRight:
        val sumIntegers = (list :\ 0)((item, accumulator) => accumulator + item)
        

Please remember not to get yourself mixed-up with the parameters location. Not a very sweet syntactic sugars, aren’t they? 🙂 This concludes my post for today. Please leave feedbacks below if you have any.

Advertisement

Simply Scala – foreach

In this post I just want to give a very small example of Scala’s conciseness. Since the program is the evolutionised version of Java, the code will be match against Java. The example given here is just in simply creating a List containing three values and then displaying each one of them.

Java code:

List<Integer> list = new ArrayList<Integer>(){{
 add(1);
 add(3);
 add(5);
}};
for (int l: list) {
  System.out.println(l);
}

Scala code:

// Initiate the list.
val l = List(1,3,5)

// For every item in the list, represented as 'n', display its value.
l.foreach { n =>
  println(n)
}

At a glance you can see that the latter is more concise than the former. But hey, it’s actually still a bit redundant. Why do we still need to redefine the variable inside the loop? The code can still be simplified a bit more.

// Initiate the list.
val l = List(1,3,5)

// Display every value inside the list.
l.foreach { println(_) }

Inside the for-loop bracket, Scala considers the underscore (_) as the active item of the list. But, seriously, do we even need the underscore? I mean, we just want to println the value for each item in the list, right? So…

// Initiate the list.
val l = List(1,3,5)

// Display every value inside the list.
l.foreach { println }

But… wait, for this example, we can actually remove the bracket since it’s just executing one line of code for each item (this also applies for the Java codes above, BTW). Also, Scala has a syntactic sugar that allows you to take out the dot(.) in calling an object’s method. So, let’s try to apply these into the code:

// Initiate the list.
val l = List(1,3,5)

// Display every value inside the list.
l foreach println

Oh gosh! it’s even simpler! It cannot possibly go much further than this, right? Well, not really. You can simplify the code above a bit more by inlining the List directly into the loop.

// Create a list and display each value.
List(1,3,5) foreach println

There you go. One line. And I would argue that it’s even more readable than the 1st one.

Simply Scala – Introduction

Being a relatively new programming language, Scala has been gaining popularity since its debut in year 2008 by Martin Ordersky, the inventor. It’s often considered as an evolved version of Java. There are a number of reasons why this is so:

1. It’s concise.

Martin takes notice of the common design patterns encountered during the development and so design this language to simplify many boilerplates. In general, one line of Scala may represent up to 5-8 lines of Java programs. Or even more.

2. It’s interoperable with Java programs.

One critical advantage of Scala is its operability with Java programs. Since it’s built on top of JVM, the compiled scala files, which are .class files, are cooperative with .class files generated from java programs.

3. It supports hybrid functional-imperative paradigm.

I’m still trying to find a way to explain what functional paradigm is. Most likely you have been programming for a while then you would have encountered, or even use, this model.

A quick comparison between imperative and functional paradigm is based on this question as a base mindset as you develop the system:

  1. Imperative: What do you want to do?
  2. Functional: What do you want?

I won’t go deep into this. Another article dedicated about this not-so-new programming paradigm is required in order to provide

There are still other strong advantages offered by Martin through this language. And of course, just as a coin has two sides, Scala also has its strong disadvantages as well, which are mostly rooted at this: It’s a very complex type system, which admittedly seem rather intimidating at first. This indicates several rooms for improvement, especially for its documentation.

Don’t get it wrong. It has already had decent community support and comprehensive documentation. I’m not talking about quantity of documentations, but quality (simplicity). Those playing around with Scala in Eclipse may sometimes cringe when you see the error compile message. It’s not always the case, though sometimes it does.

I won’t get too far here since this is just my simple introduction of what Scala is about.

Parameter Mutation

In short, do not mutate the parameter variables. It is very error-prone and it makes bug-tracing more difficult.

This is what I meant with parameter mutation.

public int[] sortNumber(int[] input) {
  for (int i=0; i<input.length-1; i++)
    for (int j=i+1; j<input.length; j++) {
      if (input[i]>input[j]) {
        int temp = input[i];
        input[i] = input[j];
        input[j] = temp;
      }
    }
  }
  return input;
}

The code shown above is an example of a bad code. Now, let’s look at this code below:

int[] numbers= new int[]{1,3,5,4,2};
int[] sortedNumber = sortNumber(numbers);

// Display the contents
for (int number: numbers) {
  System.out.print(number," "); // "1,2,3,4,5" will be printed.
}

Now as you see the sortNumber function above mutates the original data. This might not seem like a problem for you if you are the one programming the API. But when another programmer steps in and try to use the same function, it’s likely to cause a headache.
Example is always the easiest thing to do to clear things up:

int[] numbers = new int[]{1,3,5,4,2};
int[] sortedNumbers = sortNumber(numbers); // sortedNumbers = {1,2,3,4,5}
int[] reversedNumbers = reverseNumber(numbers); // reversedNumbers = {5,4,3,2,1}

As you see, the original variable (numbers) contains the unsorted value. When the sortNumber function is called and {1,3,5,4,2} is passed in, the method will return the expected array of sorted integers {1,2,3,4,5}.

The problem arises when the new programmer tries to use another function (reverseNumber in this example) using the same variable (numbers) right after using your function. He is expecting to see {2,4,5,3,1} as the result of reversing the values {1,3,5,4,2}. Oh dear he is likely to be surprised when he sees that the returned value is not as he expected.

Let’s have a quick look at some Math lesson regarding function (mapping) operation.

y1 <-- f1(x)
y2 <-- f2(x)

Now, when you call function f1 using parameter x, is it going to change the parameter x? No? Bingo, you’re right! It doesn’t make sense if the x value changes after f1 function is called.

The same thing should apply in programming as well. When you apply a function to a parameter. Do not change the parameter value in your method. If it’s really necessary, make a defensive copy of the parameter or clone the parameters and assign it to a new variable. Then you’ll be able to play around with that new variable freely without worrying about spoiling the original parameter values.

There are a few exceptions when the passed parameter variables are mutated. But in general, preventing the variable mutation is a better choice.