Old blog: Map in Java

(Found in my years old defunct blog. Less relevant now that Java is getting lambdas.)

Scheme

(map fn lst ...)

;;  ==> list
      

map is a higher order function that applies the function fn of n arguments to each element in the lists lst ...

Java has no map. Enhanced for isn't adequate for the following reasons:

• No return value: Since for is a control structure, not a function, it doesn't return anything useful. This means a data structure has to be created beforehand, and added to at each iteration of the for loop.
• No function arguments: This is not for's problem. Functions (methods) are not first class in Java.
• One iterable only: The enhanced for loop can only iterate over one Iterable data structure. map can operate on any number of lists.

Examples

Simple one list mapping

Scheme

(define squares (list 1 4 9 16))

(define (sqrts nums)
  (map sqrt nums))

(sqrts squares)

;;  ==> (1 2 3 4)
      

Java

/* No generics for clarity.  Assume also the existance of a static
   method `toList' that takes an Array and returns an ArrayList. */

List squares = toList(new Integer[] {1, 4, 9, 16});

List sqrts(List nums) {
    List out = new ArrayList();
    for (Integer i : nums)
        out.add(Math.sqrt(i));
    return out;
}

sqrts(squares);

//  ==> [1, 2, 3, 4]
      

Multiple list mapping

Scheme

(define even (list 2 4 6 8))
(define odd (list 1 3 5 7))

(define (sums . lists)
  (apply map + lists))

(sums even odd)

;;  ==> (3 7 11 15)
      

Java

/* Assume the existance of a static method `isSameLength' that tests
   whether all Lists in an array are the same length. */

List even = toList(new Integer[] {2, 4, 6, 8});
List odd = toList(new Integer[] {1, 3, 5, 7});

List sums(List... lists) {
    List out = new ArrayList();
    if (!isSameLength(lists))
        throw new RuntimeException("Lists must have same length.");
    int numargs = lists.length;
    int length = lists[0].size();
    for (int i = 0; i < length; i++) {
        int val = 0;
        for (int k = 0; k < numargs; k++)
            val += lists[k].get(i);
        out.add(val);
    }
    return out;
}

sums(even, odd);

//  ==> [3, 7, 11, 15]
      

The problem with this is that it isn't generalised.

Map in Java

First we'll need a something that acts as a first-class function.

Java

public interface Proc {

    public Object apply(Object... args);

}
      

Next, a static map method.

Java

public static List map(Proc proc, List... lists) {
    List out = new ArrayList();
    if (!isSameLength(lists))
        throw new RuntimeException("`map' requires lists of identical length");
    int numargs = lists.length;
    int length = lists[0].size();
    for (int i = 0; i < length; i++) {
        Obj[] args = new Obj[numargs];
        for (int k = 0; k < numargs; k++)
            args[k] = lists[k].get(i);
        out.add(proc.apply(args));
    }
    return out;
}
      

Now, the multiple lists example again.

Java

List even = toList(new Integer[] {2, 4, 6, 8});
List odd = toList(new Integer[] {1, 3, 5, 7});

Proc sum = new Proc() {
    public Object apply(Object... args) {
        return (Integer)args[0] + (Integer)args[1];
    }
};

List sums(List... lists) {
    return map(sum, lists);
}

sums(even, odd);

//  ==> [3, 7, 11, 15]
      

Much shorter, but with some limitations:

• It doesn't use generics, and therefore
• requires casting in Proc implementations; and
• it is hardcoded to return an ArrayList.

Parametrized map

First, Proc is changed.

Java

public interface Proc1<R, A> {

    public R apply(A arg);

}

public interface Proc2<R, A, B> {

    public R apply(A argA, B argB);

}

public interface ProcN<R, A, B,..., N> {

    public R apply(A argA, B argB,..., N argN);

}
      

And a parameterized map.

Java

public static <R, A, X extends List<R>> X map(Proc1<R, A> proc, X out, List<A> list) {
    for (A a : list)
        out.add(proc.apply(a));
    return out;
}

public static <R, A, B, X extends List<R>> X map(Proc2<R, A, B> proc,
        X out, List<A> listA, List<B> listB) {
    if (!isSameLength(listA, listB))
        throw new RuntimeException("`map' requires lists of identical length.");
    int length = listA.size();
    for (int i = 0; i < length; i ++)
        out.add(proc.apply(listA.get(i), listB.get(i));
    return out;

// And so on up to `map<R, A, B,..., N, X>.
      

The example would now be:

Java

List even = toList(new Integer[] {2, 4, 6, 8});
List odd = toList(new Integer[] {1, 3, 5, 7});

Proc2<Integer, Integer, Integer> sum = 
    new Proc<Integer, Integer, Integer>() {
        public Integer apply(Integer argA, Integer argB) {
            return argA + argB;
        }
    };

List sums(List listA, List listB) {
    return map(sum, new ArrayList(), listA, listB);
}

sums(even, odd);

//  ==> [3, 7, 11, 15]
      

The cost of parameterizing

The obvious limitation of the generic implementation is that arbitrary numbers of arguments are no longer supported in ProcN or map.

Reduce

reduce is easily written on top of Proc2.

Java

public static <R, A> R reduce(Proc2<R, R, A> proc, List<A> list, R initial) {
    int size = list.size();
    R out = initial;
    for (A a : list)
        out = fun.apply(out, a);
    return out;
}

List nums = toList(new Integer[] {1, 2, 3, 4});

Integer squareSum(List list) {
    return reduce(new Proc2<Integer, Integer, Integer>() {
        public Integer apply(Integer a, Integer b) {
            return a + (b * b);
        }
    }, list, 0);
}

squareSum(nums);

//  ==> 30