Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Functional Programming for the Uninitiated

DZone's Guide to

Functional Programming for the Uninitiated

This post addresses functional and declarative programming by way of functional thinking, looking further into each element of a solution.

· Java Zone ·
Free Resource

Get the Edge with a Professional Java IDE. 30-day free trial.

Yes, admit it, you must be thinking it as you're reading this: yet another post on functional programming. I do not intend to shed some new light on a heated debate between OO and FP. Instead, I'm going to pay tribute to those authors who have helped peel FP to its bare bones.

Being a Java developer, the starting block could only be Functional Programming for Java Developers by Dean Wampler.

Conceptually, functional programming is all about:

  • A core set of fundamental data structures, with lists being the common and basic choice, acting as data carriers, in addition to a toolkit to operate on this data. This toolkit is made of combinators (map, fold/reduce, filter) that open the door for virtually endless transformations. 
  • The variability of behavior that used to be materialized through polymorphism in OO takes a different form: lambda functions. With the help of the combinators, you can pass functions to your data holder (taking the form of streams in Java 8), and they are applied to each element in that stream.
  • Declarative programming can have a multitude of meanings, as described by Robert Harper. As I'm still in my functional thinking infancy, I'm inclined to embrace three of his definitions (for lack of understanding of the others):
    1. “Declarative” means “high-level:” The yardstick that I will be using here is very subjective, but I find that this heuristic helps me: The closer the code I write is to natural language, the higher level it feels. For example, suppose I have the top football scorers of all history, each one having a number of goals scored in a given season. How can I get a ranking of players by goals scored in decreasing order? First, the Player class:
      class Player {
              String name;
              int goals;
      
              Player(String name, int goals) {
                  this.name = name;
                  this.goals = goals;
              }
      
              public String getName() {
                  return name;
              }
      
              public int getGoals() {
                  return goals;
              }
          }

      The solution:
      Stream<Player> allTimeBestScorers = Stream.of(new Player("Luis Suarez", 14),
        new Player("Wayne Rooney", 13), new Player("Fancesco Totti", 14),
        new Player("Didier Drogba", 15), new Player("David Villa", 12),
        new Player("Robbie Keane", 15), new Player("Samuel Eto'o", 16),
        new Player("Zlatan Ibrahimovic", 17), new Player("Lionel Messi", 20),
        new Player("Cristiano Ronaldo", 20));
      
        allTimeBestScorers.collect(
           Collectors.groupingBy( 
            Player::getGoals,
            () -> new TreeMap<>(Comparator.reverseOrder()), 
            Collectors.toList())
         ).forEach((key,value) ->
           System.out.println(key + " goal(s):" + value.stream().map(Player::getName).collect(Collectors.joining(","))) );

      The output:
      20 goal(s):Lionel Messi,Cristiano Ronaldo
      17 goal(s):Zlatan Ibrahimovic
      16 goal(s):Samuel Eto'o
      15 goal(s):Didier Drogba,Robbie Keane
      14 goal(s):Luis Suarez,Fancesco Totti
      13 goal(s):Wayne Rooney
      12 goal(s):David Villa

      First, note how succinct the solution in the functional style is. Here is my one-to-one correspondence between "high level" and the implementation:
      • group players by -> Collectors.groupingBy
      • group by what? the goals they scored of course -> Player::getGoals
      • in which data structure? A map -> new TreeMap<>
      • top scorers first? no problemo -> Comparator.reverseOrder()
      • finally, how should the players with the same number of goals be arranged? a list is the simplest choice -> Collectors.toList().
      • present the output -> forEach(key,value), it does not really matter if it is not clear what is happening here.

    2. “Declarative” means "not imperative:"  I've been playing around lately with a somewhat classical problem of rotating an array to the left by x positions. In the imperative style, I could come up with two possible solutions, one that requires extra space, while the other requires extra computation.  First, the simple solution with a temporary array:
      public static IntStream rotateWithExtraSpace(int[] elements, int shift) {
              int effectiveShift = shift % elements.length;
              if (effectiveShift > 0) {
                  int[] temp = new int[effectiveShift];
                  int j = 0;
                  for (; j < effectiveShift; j++) {
                      temp[j] = elements[j];
                  }
                  for (; j < elements.length; j++) {
                      elements[j - effectiveShift] = elements[j];
                  }
                  for (int i = 0; i < temp.length; i++) {
                      elements[j - temp.length + i] = temp[i];
                  }
              }
              return Arrays.stream(elements);
          }

      Then the "dreaded" recursive solution, albeit it could be further improved:
          private static IntStream rotateRecursively(int[] elements, int shift) {
              int effectiveShift = shift % elements.length;
              doRotate(elements, effectiveShift, 0, elements.length);
              return Arrays.stream(elements);
          }
      
          private static void doRotate(int[] elements, int shift, int from, int to) {
              if (shift == 0)
                  return;
              for (int j = from + shift; j < to; j++)
                  swap(elements, j, j - shift);
              int translated = ((to - from) / shift) * shift + from;
              int low = to - shift;
              doRotate(elements, (translated - low)%shift , low, to);
          }

      If there is one thing to be noted here, it is how "low level" these solutions are. If you were not given a context, you couldn't tell what exactly is happening here. I must confess that I had to play hard at times with the different indices to get it right. This is the land of imperative programming: temporary variables, adjustments, mutations. Everything to make your head spin when you do not get it right.

    3. “Declarative” means "what, not how:" I will present here an alternative solution to the array shifting problem. Let me first describe it, then show you how it translates to code. I'm gonna use a stack of queues. The first queue to be pushed onto the stack will be filled up to the number of elements to be rotated, then all subsequent elements will be added to a different queue on top of the previous one. So this is the what, and this is it in Java 8:
      public static IntStream functionalRotation(int[] elements, final int shift) {
              Supplier<Stack<Queue<Integer>>> supplier = () -> {
                  Stack<Queue<Integer>> stack = new Stack<>();
                  Queue<Integer> queue = new LinkedList<>();
                  stack.push(queue);
                  return stack;
              };
              BiConsumer<Stack<Queue<Integer>>, Integer> accumulator = (stack, element) -> {
                  if (stack.size() > 1 || stack.peek().size() < shift) {
                      stack.peek().add(element);
                  } else {
                      Queue<Integer> shiftedQueue = new LinkedList<>();
                      shiftedQueue.add(element);
                      stack.push(shiftedQueue);
                  }
              };
              BinaryOperator<Stack<Queue<Integer>>> combiner = (left, right) -> {
                  if (left.isEmpty())
                      return right;
                  else {
                      left.addAll(right);
                      return left;
                  }
              };
              Function<Stack<Queue<Integer>>, IntStream> finisher = acc ->
              {
                  Queue<Integer> shifted = new LinkedList<>();
                  while (!acc.isEmpty()) {
                      shifted.addAll(acc.pop());
                  }
                  Integer[] ints = shifted.toArray(new Integer[]{});
                  return Stream.of(ints).mapToInt(Integer::intValue);
              };
              return Arrays.stream(elements).boxed().collect(
                      Collector.of(supplier, accumulator, combiner, finisher));
      
          }
      
      So much for a "what, not how;" I must admit that there is a little bit of both. In my defense, I would say that the how becomes native constructs: the collector, supplier, accumulator, combiner, and finisher. The what is actually captured by what each piece of the puzzle has to provide. I will provide a simple explanation of what each element provides, and I will discuss these in greater detail in a different post.
      •  The supplier gives me the data structure that I will use, a stack of queues as described above.
      • The accumulator tells me what to do when I wish to add an element to my stack.
      • The combiner is used when parallel streams are used, and I can have more than one thread doing the same logic, how can I combine all stacks produced by these different threads.
      • The finisher waits until everything is complete, and then "finishes off" by transforming my stack to an array (or IntStream here).
      The rest is all noise for the sake of this discussion. I hope that the next time you hear about functional thinking, it will hopefully make more sense. Stay tuned for a new episode.


Get the Java IDE that understands code & makes developing enjoyable. Level up your code with IntelliJ IDEA. Download the free trial.

Topics:
functional programming ,java 8 ,java

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}