High-Order Methods in Java

java

High Order Methods in Java

A higher-order method is one that takes another method as an argument. Suppose we have a class List:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/** 
 * List class defines a generic type called List, and provides
 * constructor and getter methods. 
 */
public class List<E> {
    protected boolean empty;
    protected E head;
    protected List<E> tail;

    /**
     * The first constructor creates a list consisting of a head, that is,
     * an integer and a tail, which is another list of integers.
     * @param head
     * @param tail
     */
    public List(E head, List<E> tail) {
        this.empty = false; 
        this.head = head;
        this.tail = tail;
    }
    
    /**
     *  The second constructor creates an empty list, i.e., a list
     *  with no elements.  For this list, head and tail remain
     *  undefined, calls to the corresponding getters will have to
     *  result in an exception.
     */
    public List() {
        this.empty = true;
    }
    
    /**
     * returns true if this list is empty
     */
    public boolean isEmpty() {
        return this.empty;
    }
    
    /**
     * returns the head of this list or throws an exception if the
     * list is empty
     * @throws IllegalStateException if the list is empty
     */
    public E getHead() {
        if (isEmpty()) {
            throw new IllegalStateException(
                          "Trying to access head of an empty list");
        }
        return this.head;
    }
    
    /**
     * returns the tail of this list or throws an exception if the
     * list is empty
     * @throws IllegalStateException if the list is empty
     */    
    public List<E> getTail() {
        if (isEmpty()) {
            throw new IllegalStateException(
                          "Trying to access tail of an empty list");
        }
        return this.tail;
    }
    
    public String toString() {
				return "[" + toStringAux() + "]";
    }
  
    public String toStringAux() {
       	if (isEmpty()) {
						return "";
       	} else if (getTail().isEmpty()){
						return getHead() + "";
       	} else {
						return getHead() + ", " + getTail().toStringAux();
       	}
    }
    
    @Override public boolean equals(Object o) {
				List<E> list = (List<E>) o;
				if (this.empty && list.isEmpty())
						return true;
				else if (this.isEmpty() || list.isEmpty()) {
						return false;
				}
				else if ( this.getHead().equals(list.getHead()) ) {
						return this.getTail().equals(list.getTail());
				}
				else {
						return false;
				}
		}

}

Now we can introduce a number of static high order methods to work with lists using the List class.

Map

map method takes an input List<E> and produces an output List<R>:

1
2
3
4
5
6
static<E,R> List<R> map(Function<E,R> fun, List<E> a) {
        if (a.isEmpty())
            return new List();
        else
            return new List(fun.apply(a.getHead()), map(fun, a.getTail()));
    }

map is a high order method, beacause it takes Function as its argument, and it applies this function to every element of its input list. Suppose we have an input list:

1
List<Integer> list = {1,2,3,4,5};

Then we can call the map method in this way:

1
List<Integer> result = map(x -> x*x, list);// x -> x*x is a lambda expression

Our result list would be:

1
result: {1,4,9,16,25}

Filter

filter method checks a predicate for all the elements of a list, and returns a list of those elements that satisfy the predicate:

1
2
3
4
5
6
7
8
static<E> List<E> filter(Predicate<E> pred, List<E> a) {
    if (a.isEmpty())
        return new List();
    else if (pred.test(a.getHead()))
        return new List(a.getHead(), filter(pred, a.getTail()));
    else
        return filter(pred, a.getTail());
}

Note that the output list is of the same type as the input list. Suppose we have an input list:

1
List<Integer> list = {1,2,3,4,5};

Then we can call the filter method in this way:

1
List<Integer> result = filter(x -> x % 2 == 0, list);

Our result list would be:

1
result: {2,4}

Reduce

reduce method applies a binary operator between all the elements of a list, and returns the resulting value:

1
2
3
4
5
6
static<E> E reduce(BinaryOperator<E> op, List<E> a, E identity) {
    if (a.isEmpty())
        return identity;
    else
        return op.apply(a.getHead(), reduce(op, a.getTail(), identity));
}

The identity parameter is the expected result for an empty list. Suppose we have a list:

1
List<String> list = {"all","students","are","here"};

Then we can call the reduce method in this way:

1
2
3
4
5
6
7
List<String> result = reduce((x,y) -> {
    if(x.length() >= y.length()) {
        return x;
    }else {
        return y;
    }
}, list, "");// "" is the identity

Let’s now go through the reduce method:

  1. As reduce is a recursive method, it would call itself again and again until reaching the base case. In this example, it firstly apply the binary operator between "here" and ""(which is the base case), which returns "here".

  2. Then applying the binary operator between "are" and "here", which
    returns here.

  3. Then applying the binary operator between "students" and "here", which
    returns "students".

  4. Then applying the binary operator between "all" and "students", which
    returns "students".

Therefore our result list is:

1
result: {"students"}

Appendix

The code of some useful high order methods is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.util.function.*;

public class HighOrderMethods {
    // map: a higher-order function
    // Applies a function to all the elements of a list to obtain a new list.
    // This is generic in two types, E and R, the element types of the
    // input list and output list respectively. The first argument is
    // a function from E to R, which will get "mapped" to all the
    // elements of the input list.
    static<E,R> List<R> map(Function<E,R> fun, List<E> a) {
        if (a.isEmpty())
            return new List();
        else
            return new List(fun.apply(a.getHead()), map(fun, a.getTail()));
    }

    // filter: a higher-order function
    // Checks a predicate for all the elements of a list, and returns
    // a list of those elements that satisfy the predicate.
    // Note that the output list is of the type as the input list.   
    static<E> List<E> filter(Predicate<E> pred, List<E> a) {
        if (a.isEmpty())
            return new List();
        else if (pred.test(a.getHead()))
            return new List(a.getHead(), filter(pred, a.getTail()));
        else
            return filter(pred, a.getTail());
    }

    // reduce: a higher-order function
    // Applies a binary operator between all the elements of a list,
    // and returns the resulting value.
    // The identity parameter is the expected result for an empty list.
    static<E> E reduce(BinaryOperator<E> op, List<E> a, E identity) {
        if (a.isEmpty())
            return identity;
        else
            return op.apply(a.getHead(), reduce(op, a.getTail(), identity));
    }
    
    // fold: a higher-order function, more flexible than reduce
    // Applies a binary operator between all the elements of a list,
    // and returns the resulting value.
    // The identity parameter is the expected result for an empty list.
    static<E,R> R fold(BiFunction<E,R,R> op, List<E> a, R identity) {
        if (a.isEmpty())
            return identity;
        else
            return op.apply(a.getHead(), fold(op, a.getTail(), identity));
    }
    
    // Sum all the elements of an integer list
    // This uses the higher-order function reduce.
    static Integer sumShort(List<Integer> a) {
        return reduce((x,y) -> x+y, a, 0);
    }

    // Select all the positive values of an integer list.
    // This uses the higher-order function filter.
    static List<Integer> positives(List<Integer> a) {
    	return filter((x) -> x >= 0, a);
    }

    // Append two generic lists
    // This uses the higher-order function fold.
    static<E> List<E> appendShort(List<E> a, List<E> b) {
        return fold((x,y) -> new List(x,y), a, b);
    }
}