FP in a Nutshell

Yes, admit it, you must be thinking it as you're reading this, yet another post on functional programming. I do not intend here to shed some new light on a heated debate between OO and FP. Instead, I'm gonna 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 on 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 3 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 well: The closer the code I write 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 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 structue? 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 2 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, is how "low level" these solutions are. If you were not given a context, you couldn't tell what is exactly 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 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 would hopefully make more sense. Stay tuned for a new episode.