(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