Friday, September 30, 2016

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.
       

No comments:

Functional Java: Hate the player not the game

We've all heard it over and over, Java 8 is not really functional programming. I admit that features like tail call optimization, closu...