Comparing Imperative and Functional Algorithms in Java 8


Mario Fusco’s popular tweet impressively shows what the main difference between imperative and functional approaches to similar algorithms really is:

Both algorithms do the same thing, they’re probably equally fast and reasonable. Yet, one of the algorithms is much easier to write and read than the other. The difference lies in the fact that in imperative programming, different algorithmic requirements are spread throughout the code block, when in functional programming, each requirement has its own little line of code. Compare:

  • Green: Error handling
  • Blue: Stop criteria
  • Red: IO operations
  • Yellow: “Business logic”

Functional programming doesn’t always beat imperative programming as displayed in other examples on the jOOQ blog:

But here’s an example from Stack Overflow by user Aurora_Titanium, where the difference is as clear as in Mario Fusco’s example:

Calculating the Duplicate Values in an Array

The idea is to calculate the sum of all those values that are duplicate in a set of values. For instance, the following array:

int[] list = new int[]{1,2,3,4,5,6,7,8,8,8,9,10};

… should yield as a result something like:

Duplicate: 8. Sum of all duplicate values: 24

The imperative approach

One of the answers by user Volkan Ozkan takes an imperative approach and calculates the sum as such:

int[] array = new int[] { 
    1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 9, 10 
};

int sum = 0;
for (int j = 0; j < array.length; j++)
{
    for (int k = j + 1; k < array.length; k++) 
    {
        if (k != j && array[k] == array[j])
        {
            sum = sum + array[k];
            System.out.println(
                "Duplicate found: " 
              + array[k]
              + " " 
              + "Sum of the duplicate value is " + sum);
        }
    }
}

The approach works only for sorted arrays where duplicates appear right after one another. In that case, however, it is probably an optimal solution in terms of performance, if performance really matters to this algorithm.

The functional approach

If a slight decrease of performance is acceptable to you (boxing ints, collecting them into maps), and it probably is, you can replace the above difficult-to-read code with the following bit of functional Java-8-style logic, which communicates much more clearly what it does:

int[] array = new int[] { 
    1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 9, 10 
};

IntStream.of(array)
         .boxed()
         .collect(groupingBy(i -> i))
         .entrySet()
         .stream()
         .filter(e -> e.getValue().size() > 1)
         .forEach(e -> {
             System.out.println(
                 "Duplicates found for : " 
               + e.getKey()
               + " their sum being : " 
               + e.getValue()
                  .stream()
                  .collect(summingInt(i -> i)));
         });

or, with explanations:

int[] array = new int[] { 
    1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 9, 10 
};

// Create a Stream<Integer> from your data
IntStream.of(array)
         .boxed()

// Group values into a Map<Integer, List<Integer>>
         .collect(groupingBy(i -> i))

// Filter out those map values that have only 
// 1 element in their group
         .entrySet()
         .stream()
         .filter(e -> e.getValue().size() > 1)

// Print the sum for the remaining groups
         .forEach(e -> {
             System.out.println(
                 "Duplicates found for : " 
               + e.getKey()
               + " their sum being : " 
               + e.getValue()
                  .stream()
                  .collect(summingInt(i -> i)));
         });

(note that the functional approach calculates sums for each duplicate value, not an overall sum, like the imperative approach. From the original question, this requirement wasn’t very clear)

As we’ve stated in a previous article on our blog, the power of functional programming via an API like the Java 8 Stream API is the fact that we’re approaching the expressive power of SQL-style declarative programming. We’re no longer concerned with remembering individual array indexes and how to calculate them and store intermediate results into some buffers. We can now focus on the really interesting logic, such as: “what’s a duplicate?” or “what sum am I interested in?”

Read on about how SQL compares to Java 8 Streams:

Common SQL clauses and their equivalents in Java 8 Streams

6 thoughts on “Comparing Imperative and Functional Algorithms in Java 8

  1. I’m just stirring, so don’t take seriously.😉

    If “you can replace the above difficult-to-read code with the following bit of functional Java-8-style logic, which communicates much more clearly what it does:”, why do you need to redisplay the code with explanations every time you give an example?:-)

    Seriously, though, functional requires looking at a problem in a different way. When you are working on large, imperative codebases, trying to introduce functional code is not necessarily easy or wise. When debugging issues, having to switch between imperative and functional is distracting, at best.

    Each approach has its place but randomly mixing idioms in code, I feel, will make code quality worse in the short term. Having this become yet another “religious” issue is bad for developers – the dividing lines are being clearly drawn, as shown in the tweet’s comments.

    Of course, every team is different and the abilities of the team members is important, so different projects will see different benefits.

    But no-one seems to be considering the plight of maintenance engineers. Not every developer develops new code. We have recently seen the move from Swing to JavaFX, the mixing of imperative and functional, and the soon-to-be move to modularity in Java 9. Maintenance engineers have to cope with all of these, often all mixed up, and will have to for many years yet to come. I recently saw a post that showed how many places were still using Java 6 & 7. These will encounter a lot of disruption when upgrading.

    Interesting times!

    • why do you need to redisplay the code with explanations every time you give an example

      Nice one😉

      I completely agree with you. And often, imperative code is better at expressing what it does than its functional counterpart. Especially in Java, where a lot of boilerplate is needed because of backwards-compatibility. I think this is also reflected in the article, where I mentioned:

      Functional programming doesn’t always beat imperative programming as displayed in other examples on the jOOQ blog […]

      Along the lines of your argument, I have helped maintain an E-Banking system of a local company here, in the past. There had been 5 different approaches in the same system when it came to tackling database access and data transfer models. In the end, they replaced most of their existing approaches with jOOQ, but it took ages to migrate. Some code fragments still use EJB 2.0 EntityBeans…

      Adding new techniques should be a strategic decision. Just like changing style guides, by the way:)

  2. The example by Mario Fusco is rather unfair and doesn’t compile, but we all know this. What you’re writing about the algorithm by Volkan Ozkan belongs probably to a different algorithm (the one by the OP) as Volkan’s nested loops are by no means fast and need no sorting.

    If you don’t insist on the output for each duplicate found, then there’s a hard to beat Guava based purely imperative solution:

    int result = 0;
    for (Multiset.Entry e : HashMultiset.create(Ints.asList(array))) {
        if (e.getCount() > 1) result += e.getCount() * e.getElement();
    }
    

    It’s all about having the right data structures and methods. The shortest imperative solution is *always* something like doItAllImperatively(input) and you can imagine the functional counterpart.

    I guess that for most tasks, the functional approach will be slightly shorter and slightly harder to read. In some cases it’ll really excel, but often it’ll get misused just “because I can”. The switching between the approaches may be a big problem and so may be the new TIMTOWTDI. Not to speak about the beginners getting a bigger shinier gun for their feet.

    • Very nice solution using Multiset. Indeed, there’s always more than one way to do things, and with FP, there are even dozens of new ways to do things if you use more sophisticated libraries than Stream. The article also contains such a disclaimer:

      Functional programming doesn’t always beat imperative programming as displayed in other examples on the jOOQ blog

      In fact, every time I translated a common imperative algorithm to functional (in Java 8), I came to a similar conclusion: I like it because I wrote it (and I managed to actually write it), but is it all that better? Hmm…

      • “I like it because I wrote it (and I managed to actually write it), but is it all that better?”

        Well the new Apple thing is cool, but do I need it?😉 just kidding.

        I’m always wondering the same thing and sometimes I force myself to find a solution in lambda expressions, but in the end I mix imperative and declerative (sic!)… shame on me!

        • With that Apple thing: The answer is: No. It’s a waste of money.

          And no: There’s no shame in mixing styles. We’ll just wait 4-5 years until someone writes a new design patterns book. Until then, we’ll add value to our customers’ businesses by writing software that works:)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s