Write a purely functional Bubble Sort application

Neal Ford coined the term functional thinking to describe the mental shift required from developers trained primarily in object-oriented programming, who want to integrate functional programming concepts and techniques into their practice. I applied this concept in my two-part tutorial, “Functional programming for Java developers.” In Part 1, I introduced five functional programming techniques written in JavaScript, then in Part 2 we refactored those code examples using the equivalent Java code. Next, we refactored a number of those examples again, this time using functional programming language features introduced in Java 8.

Now I invite you to one last exercise in functional thinking, refactoring the Sort application from “Functional programming for Java developers, Part 2” to integrate a variety of functional techniques. One again we’ll work through several iterations, improving the code as we go along.

Refactor #1: The classic bubble sort, with a functional twist

The original Sort application show below is far from functional. About the only thing functional about it is the sort() method’s parameter list. Thanks to the passed comparator, that list indicates that sort() is a first-class function.

Listing 1. The original, object-oriented bubble sort (Sort.java)

import java.util.Comparator;
public class Sort
{
   public static void main(String[] args)
   {
      String[] innerplanets = { "Mercury", "Venus", "Earth", "Mars" };
      dump(innerplanets);
      sort(innerplanets, new Comparator<String>()
                         {
                            @Override
                            public int compare(String e1, String e2)
                            {
                               return e1.compareTo(e2);
                            }
                         });
      dump(innerplanets);
      sort(innerplanets, new Comparator<String>()
                         {
                            @Override
                            public int compare(String e1, String e2)
                            {
                               return e2.compareTo(e1);
                            }
                         });
      dump(innerplanets);
   }
   static <T> void dump(T[] array)
   {
      for (T element: array)
         System.out.println(element);
      System.out.println();
   }
   static <T> void sort(T[] array, Comparator<T> cmp)
   {
      for (int pass = 0; pass < array.length - 1; pass++)
         for (int i = array.length - 1; i > pass; i--)
            if (cmp.compare(array[i], array[pass]) < 0)
               swap(array, i, pass);
   }
   static <T> void swap(T[] array, int i, int j)
   {
      T temp = array[i];
      array[i] = array[j];
      array[j] = temp;
   }
}

Recall that functional programming is expression-oriented and abstains from using statements. With those guidelines in mind, it becomes clear that we can make the Sort application more functional by eliminating dump()‘s for statement and sort()‘s for and if statements.

We’ll need to replace for and if with equivalent higher-order functions (aka first-class functions). Because we might want to reuse these functions, we’ll stick them in a library. Listing 2 presents an FL (Functional Library) class.

Listing 2. Sort refactored with higher-order functions and a functional library (FL.java)

interface Function<T>
{
   void apply(T t);
}
public final class FL
{
   private final static Function<Integer> FEMPTY = 
      new Function<Integer>() { public void apply(Integer i) {} };
   public static void forEach(final int start, final int end, final boolean inc,
                              final Function<Integer> f)
   {
      ifThen(start != end, 
             new Function<Integer>()
             {
                @Override
                public void apply(Integer i)
                {
                   f.apply(start);
                   forEach(inc ? start + 1 : start - 1, end, inc, f);
                }
             });
   }
   public static void ifThen(boolean predicate, Function<Integer> onTrue)
   {
      ifThenElse(predicate, onTrue, FEMPTY);
   }
   public static void ifThenElse(boolean predicate, Function<Integer> onTrue,
                                 Function<Integer> onFalse)
   {
      ifThenElse1(predicate ? onTrue : onFalse);
   }
   private static void ifThenElse1(Function<Integer> f)
   {
      f.apply(0);
   }
}

About the code

Listing 2 begins by defining a Function type. This type should be public and located in its own source file because it will be accessed from outside the library. However, it’s convenient to place it in the same source file as the FL class.

The FL class declares public forEach(), ifThen(), and ifThenElse() methods that represent higher-order functions. I don’t need ifThenElse() for this conversion, but it might come in handy in another context.

The forEach() method is invoked with arguments passed to its start, end, inc, and f parameters:

• start is the initial integer index of the loop.
• end is one more than the final index of the loop.
• inc is true for an index-increasing loop and false for an index-decreasing loop.
• f is the function to execute for each loop iteration.

Recursion and the ?: operator

forEach() uses recursion to handle the looping, which is typical in functional programming. It invokes the ifThen() method to handle the base case, in which recursion ends when start equals end.

The ifThen method is invoked with arguments passed to predicate and onTrue. We really should give predicate a function type, but in this case we’ll leave it as boolean for convenience.

Recall from Listing 2 that I implemented ifThen() in terms of ifThenElse(), which I thought I might need when I started the project. Because ifThen() has no else part, we now pass a default FEMPTY function to ifThenElse()‘s onFalse parameter.

The ifThenElse() method uses the ?: operator to decide between the onTrue or onFalse function. Because this operator must return a value, and because we want ifThenElse() to have a void return type (in order to avoid having to specify a return statement), we write the ifThenElse() to invoke the ifThenElse1() helper function. The helper then invokes the function argument’s apply() method with argument 0.

We could have designed ifThen() and ifThenElse() to take an additional argument that would ultimately be passed to apply(), but we don’t need that capability for the functional sort application.

Refactor #2: A pre-Java 8 functional Sort application

We’ve refactored the original Sort application with a few functional programming features. Now we’re ready to write a completely functional Sort application. In this case, we’ll use functional programming techniques that pre-date Java 8 . Listing 3 presents the source for the FuncSort application.

Listing 3. The functional sort application, version 1 (FuncSort.java)

import java.util.Comparator;
public class FuncSort
{
   public static void main(String[] args)
   {
      String[] innerplanets = { "Mercury", "Venus", "Earth", "Mars" };
      dump(innerplanets);
      sort(innerplanets, new Comparator<String>()
                         {
                            @Override
                            public int compare(String e1, String e2)
                            {
                               return e1.compareTo(e2);
                            }
                         });
      dump(innerplanets);
      sort(innerplanets, new Comparator<String>()
                         {
                            @Override
                            public int compare(String e1, String e2)
                            {
                               return e2.compareTo(e1);
                            }
                         });
      dump(innerplanets);
   }
   static <T> void dump(final T[] array)
   {
      FL.forEach(0, array.length, true,
                 new Function<Integer>()
                 {
                    @Override
                    public void apply(final Integer i)
                    {
                       System.out.println(array[i]);
                    }
                 });
      System.out.println();
   }
   static <T> void sort(final T[] array, final Comparator<T> cmp)
   {
      FL.forEach(0, array.length - 1, true,
                 new Function<Integer>()
                 {
                    @Override
                    public void apply(final Integer pass)
                    {
                       FL.forEach(array.length - 1, pass, false,
                                  new Function<Integer>()
                                  {
                                     @Override
                                     public void apply(final Integer i)
                                     {
                                        FL.ifThen(cmp.compare(array[i], 
                                                              array[pass]) < 0, 
                                                  new Function<Integer>()
                                                  {
                                                     @Override
                                                     public void apply(Integer z)
                                                     {
                                                        swap(array, i, pass);
                                                     }
                                                  });
                                     }
                                  });
                    }
                 });
   }
   static <T> void swap(T[] array, int i, int j)
   {
      T temp = array[i];
      array[i] = array[j];
      array[j] = temp;
   }
}

Assuming that you have the source files from Listing 2 and Listing 3 in the same directory, compile them as follows:

javac *.java

Run the resulting application as follows:

java FuncSort

You should observe the same output you saw from the Sort application in Part 2.

The dump() and sort() methods are certainly more functional than their Listing 2 counterparts. They’re also more verbose and harder to read.

Refactor #3: A functional Sort for Java 8

In the previous example we used functional programming techniques to convert object-oriented code to a more functional paradigm. Now let’s see what happens when we use Java 8’s functional programming capabilities to result in a fully functional Java Sort application.

Listing 4. FuncSort.java (version 2)

import java.util.Arrays;
import java.util.Comparator;
public class FuncSort
{
   public static void main(String[] args)
   {
      String[] innerplanets = { "Mercury", "Venus", "Earth", "Mars" };
      dump(innerplanets);
      sort(innerplanets, (e1, e2) -> e1.compareTo(e2));
      dump(innerplanets);
      sort(innerplanets, (e1, e2) -> e2.compareTo(e1));
      dump(innerplanets);
   }
   static <T> void dump(T[] array)
   {
      Arrays.stream(array).forEach(System.out::println);
      System.out.println();
   }
   static <T> void sort(T[] array, Comparator<T> cmp)
   {
      System.arraycopy(Arrays.stream(array).sorted(cmp).toArray(), 0, array, 0,
                       array.length);
   }
}

About the code

The dump() and sort() methods are trivial because we’ve leveraged the Java’s Streams API. The Arrays.stream(array) expression transforms an array into a stream. The sorted() intermediate operation returns a new stream consisting of the elements of the old stream, sorted according to the provided Comparator. The toArray() terminal operation returns an array containing the sorted stream’s elements.

Conclusion

By now you’ve probably figured out that I cheated in how I set up this example. The fully functional program in Listing 4 doesn’t implement a Java 8 version of the Bubble Sort algorithm like I said it would: instead, it relies on whatever algorithm is used by the sorted() operation. Not only is Bubble Sort inefficient, but a fully functional programming version of this algorithm would be unnecessarily verbose. Truly functional thinking results in functional code that is efficient and terse while still being understandable.