Is there a type-safe Java implementation of 'reduce'?

Question

I often need to run reduce (also called foldl / foldr, depending on your contexts) in java to aggregate elements of an Itterable.

Reduce takes a collection/iterable/etc, a function of two parameters, and an optional start value (depending on the implementation details). The function is successively applied to an element of the collection and the output of the previous invocation of reduce until all elements have been processed, and returns the final value.

Is there a type-safe implementation of reduce in any common java api? Google Collections seems like it should have one, but I haven't been able to find it. (possibly because I don't know what other names it would use.)

Answer 1

you could probably roll your own generic pretty easily, based on your description:

public interface Reducer<A, T>
{
    public A foldIn(A accum, T next);
}

Then using the strategy pattern:

public class Reductor<A, T>
{
    private Reducer<A, T> worker;
    public Reductor<A, T>(Reducer<A, T> worker)
    {
        this.worker = worker;
    }

    public A fold(A rval, Iterator<T> itr)
    {
        while(itr.hasNext())
        {
            A rval = worker.foldIn(rval, itr.next());
        }
        return rval;
    }
}

I'm sure there are a ton of syntax errors but that's the main point (there a few choices you could make about how to get the empty accumulator value. Then to use it on a particular iterator just define your Reducer on the fly:

Reductor r = new Reductor<A, T>(new Reducer<A, T>()
{
    public A foldIn(A prev, T next)
    {
        A rval;
       //do stuff...
       return rval;
     }
 }

 A fold = r.fold(new A(), collection.getIterator());

depending on how your iterator works this can fold left or fold right as long as the iterator goes in the right direction.

hope this helps.

Answer 2

Based on Luke's suggestion, here is a legit Java implementation:

public interface Reducer<A,T>
{
    A foldIn(A accum, T next);
}

public static <T> T reduce(final Reducer<T,T> reducer, 
        final Iterable<? extends T> i)
{
    T result = null;
    final Iterator<? extends T> iter = i.iterator();
    if (iter.hasNext())
    {
        result = iter.next();
        while (iter.hasNext())
        {
            result = reducer.foldIn(result, iter.next());
        }
    }
    return result;
}

public static <A,T> A reduce(final Reducer<A,T> reducer, 
        final Iterable<? extends T> i, 
        final A initializer)
{
    A result = initializer;
    final Iterator<? extends T> iter = i.iterator();
    while (iter.hasNext())
    {
        result = reducer.foldIn(result, iter.next());
    }
    return result;
}