Reduction Operation in functional programming

the operation "Reduce" or "Fold" is a very important operation in functional programming, as you could implement all other operations using the reduce operation. (see ProgFun course at Coursera)

Also, Java tutorial has a very straightforward illustration for Reduction in Java 8: https://docs.oracle.com/javase/tutorial/collections/streams/reduction.html

I want to talk about a case (from cobone-reviews project) that I needed low-level reduction operation.

First I have a Map<Object, List<Long>> that looks like:

{"dp.g.doubleclick.net": [0,1,0,0,0],"cobonereviews.tk": [0,1,0,0,0],"www.facebook.com": [3,4,0,0,0],"www.google.co.in": [0,1,0,0,0],"localhost:8080": [0,0,40,5,3],"l.facebook.com": [0,1,0,0,0],"www.google.com": [0,10,5,0,0],"www.google.com.sa": [0,11,0,0,0],"www.google.com.hk": [0,1,0,0,0],"www.google.ae": [0,3,0,0,0]}

I need to group each top private domain's result together, So the result would looks like:

 {  
   "localhost:8080":[  
    0,  
    0,  
    40,  
    5,  
    3  
   ],  
   "facebook":[  
    3,  
    5,  
    0,  
    0,  
    0  
   ],  
   "google":[  
    0,  
    26,  
    5,  
    0,  
    0  
   ],  
   "cobonereviews":[  
    0,  
    1,  
    0,  
    0,  
    0  
   ],  
   "doubleclick":[  
    0,  
    1,  
    0,  
    0,  
    0  
   ]  
 }  

So first I used the following method to get Top Private Domain from the Map's keys above:

 // Example: www.google.com.sa, google.com, google.eg all translated to  
 // google  
 private String getDomainName(Object referrer) {  
      try {  
           String topPrivateDomain = InternetDomainName.from(referrer.toString()).topPrivateDomain().name();  
           String publicSuffix = InternetDomainName.from(referrer.toString()).publicSuffix().name();  
           String onlyDomainName = topPrivateDomain.replace(publicSuffix, "");  
           return onlyDomainName.endsWith(".") ? onlyDomainName.substring(0, onlyDomainName.length() - 1)  
                     : onlyDomainName;  
      } catch (Exception ex) {  
           log.error(ex.getMessage());  
           return referrer.toString();  
      }  
 }  

Then, I need to use the getDomainName method above as a grouping key and then for the values, I need to concatenate the all lists under the same domain together, for example for case of facebook, I have the following map:

 "www.facebook.com":[   
  3,   
  4,   
  0,   
  0,   
  0   
  ], "l.facebook.com":[   
  0,   
  1,   
  0,   
  0,   
  0   
 ] 

And I need the result to be:

 "facebook":[   
  3,   
  5,   
  0,   
  0,   
  0   
  ]  

So, The reduction method that do the the concat operation looks like:

 collect2.entrySet().stream().collect(groupingBy(e -> getDomainName(e.getKey()),  
  reducing(new ArrayList<Long>(), e -> e.getValue(), (l1, l2) -> accumlateLists(l1, l2))));  

And here's the implementation of accumlateLists method

 private List<Long> accumlateLists(List<Long> accumlator, List<Long> list) {  
      if (accumlator.isEmpty()) {  
           return list;  
      } else {  
           for (int i = 0; i < accumlator.size(); i++) {  
                accumlator.set(i, accumlator.get(i) + list.get(i));  
           }  
           return accumlator;  
      }  
 }  

Note, In the reduction method above, we used the form:

 reducing(U identity, Function<? super T, ? extends U> mapper, BinaryOperator<U> op)  

The first parameter is the accumulator and the zero value (empty ArrayList), the second parameter is mapper, which maps the Entry object to List<Long> which is the object that will be used by the third parameter, hence the mapper Function returns object of type U the same that would be used as type parameter for the BinaryOperator (which is a BiFunction).

Complete source code would be found in this file.

Scala or Kotlin

JVM has many language based on it, many of them are famous like Groovy, Scala, Koltin and others.

In the past I've played with Scala, now I try to post the same code snippet in Scala and in Koltin (actually koltin looks like scala in many ways):

Scala Code:

// scala

object Main {
  def main(args: Array[String]): Unit = {

    val a = 10
    val b = 50
    println(apply(a, b, { (x, y) => x * y }))
    println(apply(a, b, sum))

    val l = List(1, 3, 5)
    l map { _ * 2 } filter { _ > 4 } foreach { println(_) }
  }

  def sum(a: Int, b: Int): Int = a + b

  def apply(x: Int, y: Int, f: (Int, Int) => Int) = f(x, y)
}

Koltin Code:

// kotlin

fun main(args: Array<String>): Unit {

    val a = 10
    val b = 50
    println(apply(a, b, {x, y -> x * y}))
    println(apply(a, b, ::sum))

    val l = listOf(1, 3, 5)
    l.map { it * 2 } .filter { it > 4 } .forEach { println( it ) }
}


fun sum(a: Int, b: Int): Int = a + b

fun apply(x: Int, y: Int, f: (Int, Int)-> Int) = f(x, y)

Tail Recursion

Tail recursion is special case of recursion where the function calls itself as the last statement in the method.

From wikipedia:

Tail calls can be implemented without adding a new stack frame to the call stack. 

Here's an example of Sum of Ints function that sum Integers between a and b

so when call sumOfInts(1, 4) would equals 1 + 2 + 3 + 4 = 10

First implementation using non-Tail recursion:

def sumOfInt(a: Int, b: Int): Int =

        if (a > b) 0 else a + sumOfInt(a + 1, b) // last stmt is a call to the same function and then add some value to it (non tail recursion)

The second implementation using a Tail recursion function:

def sumOfInt2(a: Int, b: Int): Int =

        sumOfAllInts(a, b, 0)                    

def sumOfAllInts(a: Int, b: Int, t: Int): Int =

        if (a > b) t else sumOfAllInts(a + 1, b, t + a)  // last stem is a call to the same function only (tail recursion)

Test

sumOfInt(1, 100000000)                        //> java.lang.StackOverflowError

sumOfInt2(1, 100000000)                       //> res2: Int = 987459712

Conclusion

The Tail recursion version using the same stack frame on each call (vs the non-tail recursion which  will use a new stack frame for each call for the reclusive method)

See this question and read the answer to understand about Tail Recursion: http://cs.stackexchange.com/questions/6230/what-is-tail-recursion

Progfun: Union two Binary Trees (week 03)

In Progfun assignment of week3 named "objsets", it is required to write some fast-engouh implementation for the union method.

Note, I am here will not show the solution for this question, I'll just give you the key to find the solution yourself.

Here's the Tree objects:

abstract class TweetSet {

    def union(that: TweetSet): TweetSet

    // other methods here..

}

class Empty extends TweetSet {

    def union(that: TweetSet): TweetSet = that

}

class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet {

    // The is the Not-so-fast implementation from the lectures

    def union(that: TweetSet) = ((left union right) union that) incl elem

}

The question again is to find a better solution for the union method (better in terms of performance as the app with such implementation will took too much time to execute)

Well, since I am not so much good in finding a solution in one shot, I go through more than a step..

First I thought in instead of making the `this` tree to include the `that` tree's nodes, I think of the opposite, which is the `that` tree to include the `this` nodes.

I wrote this -not so good -implementation that is coming from (and based on) the foreach implementation; the foreach implementation is:

def foreach(f: Tweet => Unit): Unit = {

    f(elem)

    left.foreach(f)

    right.foreach(f)

}

So, I thought of an implementation like this, but instead of applying some function to each node, no just add each node to `that` tree, So I wrote this initial implementation:

def union(that: TweetSet): TweetSet = {

    var thatVar = that

    this.foreach { x => thatVar = thatVar.incl(x) }

    thatVar

}

WOW, it worked!, So let's enhance it to comply to the courses rules, which among them is don't use vars and use recursion when possible.

The idea above is for each node in the `this` tree, include it to the `that` tree... pretty simple..

To accomplish this by recursion, we need to do the following:

1. `that` should include the element
2. the result of step #1 should be passed again to the recursion method as `that` and ask `left` start the union process over, then ask `right` to start it over again..

def union(that: TweetSet): TweetSet = ??.union(??.union(?? incl elem))

3. replace the ?? above based on your understanding and you will got the solution.

Java8, my first attempt to write simple lambda (closure)-based example

Java8 will introduce lambda expressions (a.k.a closure), So it will introduce many functional concepts to compete with other powerful langs such as scala.


I've wrote some simple example to show the powerful of functional interfaces and the shortcut syntax of lambda expressions.

I've wrote the example once by Java8 syntax and once by Java7 syntax.

public class HelloJava8{
    public static void main(String[] args){
    
        int v1 = 10, v2 = 30;
    
        int result = performOperation(v1, v2, (a, b) -> a + b);
        System.out.println("result: " + result);
        
        result = performOperation(v1, v2, (x, y) -> x - y);
        System.out.println("result: " + result);
        
        Operation op = (i, j) -> i * j;
        result = performOperation(v1, v2, op);
        System.out.println("result: " + result);
    }

    // funcationl interface, an interface with one method    
    private static int performOperation(int x, int y, Operation op){
        return op.doOperation(x, y);
    }
    
    interface Operation{
        int doOperation(int x, int y);
    }

}

Here's the example with Java7 (notice how Java8 code is much compact):

public class HelloJava7{
    public static void main(String[] args){
    
        int v1 = 10, v2 = 30;
    
        int result = performOperation(v1, v2, new Operation(){
            public int doOperation(int x, int y){
                return x + y;
            }
        });
        System.out.println("result: " + result);
        
        result = performOperation(v1, v2, new Operation(){
            public int doOperation(int x, int y){
                return x + y;
            }
        });
        System.out.println("result: " + result);
        
        Operation op = new Operation(){
            public int doOperation(int i, int j){
                return i * j;
            }
        };    
        result = performOperation(v1, v2, op);
        System.out.println("result: " + result);
    }
    
    private static int performOperation(int x, int y, Operation op){
        return op.doOperation(x, y);
    }
    
    interface Operation{
        int doOperation(int x, int y);
    }

}

Go functional the Java way (1)

Functional programming deals with functions as a High-order functions that can be used the same way the variables are used, so as the functions can by send as a parameters to other functions.

In Java, we can achieve this by sending an interface containing this simple function to some method.

If we have a function "sum" that looks like:

public static int sum(int[] arr) {
    int sum = 0;
    for (int i=0; i < arr.length; i++) {
            sum += arr[i];
    }
    return sum;
}

And we need to sum the array based on some condition, If Java supports passing functions to method, we could pass the function this way:

sum(new int[]{1, 2, 3, 4, 5}, function(int i){ return i%2 ==0 } )

But since Java doesn't, We should go the Java way doing that, notice the example below:

public class Main {
    public static void main(String[] args) {
        
        int sum = sum(new int[] {1, 2, 3, 4, 5}, new Predicate<Integer>() {
            public boolean test(Integer t) {
                return t >= 4 ;
            }
        });
        System.out.println(sum);
    }
    
    public static int sum(int[] arr, Predicate<Integer> accept) {
        int sum = 0;
        for (int i=0; i < arr.length; i++) {
            if (accept.test(arr[i]))
                sum += arr[i];
        }
        return sum;
    }
    
    interface Predicate<T>{
        boolean test(T t);
    }
}

Does the above code looks familiar?
It should, since the Collections.sort uses similar code to do custom sorting of a List.

In Java8 and according to http://www.dzone.com/links/r/why_we_need_lambda_expressions_in_java_part_1.html the syntax should be much simpler using lambda expression. It might look like Scala code:

sum(new int[]{1, 2, 3, 4, 5}, (Intger i) => i%2 == 0 )

---

Reference and code blocks from the above link.