Add a fold method for Iterables

[GoogleCodeExporter]

I find myself always wanting to iterate over a collection to aggregate the
data and wishing Google Collections had a fold operation.

An implementation can be found on StackOverflow,
<http://stackoverflow.com/questions/950751/how-to-implement-a-list-fold-in-java/
951337#951337>.

Original issue reported on code.google.com by rwallace...@gmail.com on 12 Aug 2009 at 11:37

[GoogleCodeExporter]

A possibly easier implementation is to create a new FoldFunction type.  And 
implement
foldLeft as 

    static <A, B> A foldLeft(Iterable<B> xs, A z, FoldFunction<A, B> f)
    {
        A p = z;
        for (B x : xs)
        {
            p = f.apply(p, x);
        }
        return p;
    }

    interface FoldFunction<A, B>
    {
        A apply(A a, B b);
    }

Original comment by rwallace...@gmail.com on 13 Aug 2009 at 12:07

[GoogleCodeExporter]

What about a compress() function? (Maybe there's a better name.) compress() 
would
have to return null in the case of failure. Like this:

    static <T> Iterable<T> compress(Iterable<T> iterable, CompressFunction<T> f) {
        Iterator<T> i = iterable.iterator();

        if (!i.hasNext())
            return Collections.emptyList();

        T first = i.next();
        if (!i.hasNext())
            return ImmutableList.of(first);

        Stack<T> compressed = new Stack<T>();
        compressed.push(first);

        while (i.hasNext()) {
            T t = i.next();
            T c = f.compress(compressed.peek(), t);

            if (c != null) {
                compressed.pop();
                compressed.push(c);
            } else {
                compressed.push(t);
            }
        }

        return ImmutableList.copyOf(compressed);
    }

    interface CompressFunction<T> {
        T compress(T t1, T t2);
    }

    class Range {
        int from, to;
    }

    class CompressRanges implements CompressFunction<Range> {

        public Range compress(Range r1, Range r2) {
            if (r1.from > r2.to || r1.to < r2.from)
                return null;

            Range r = new Range();
            r.from = Math.min(r1.from, r2.from);
            r.to = Math.min(r1.to, r2.to);
            return r;
        }

    }

I'd like to hear your input on this. Do my random thoughts make sense to 
anybody?

Original comment by andre.ru...@gmail.com on 13 Aug 2009 at 8:52

[GoogleCodeExporter]

I prefer the term reduce, and i'd also like to see it in the library.

{{{
/** (a, b, c, d) -> f(f(f(a, b), c), d) */
public static <T> T reduce(final Iterable<? extends T> gen, final Function2<? 
super 
T, ? super T, ? extends T> f) {
    final Iterator<? extends T> it = gen.iterator();
    if (!it.hasNext()) {
        return null;
    }
    T result = it.next();
    while (it.hasNext()) {
        result = f.apply(result, it.next());
    }
    return result;
}

/** (a, b, c, d), initial -> f(f(f(f(initial,a), b), c), d) */
public static <X,Y> X reduce(final Iterable<? extends Y> gen, final X initial, 
final 
Function2<? super X, ? super Y, ? extends X> function) {
    final Iterator<? extends Y> it = gen.iterator();
    if (!it.hasNext()) {
        return initial;
    }
    X acc = initial;
    while (it.hasNext()) {
        acc = function.apply(acc, it.next());
    }
    return acc;
}
}}}

Original comment by jvdne...@gmail.com on 14 Aug 2009 at 9:42

[GoogleCodeExporter]

This requires the inclusion of a two-argument functor interface. I've seen 
negative 
reactions on previous requests so I'm thinking there's little chance of this 
one 
getting accepted. The fact that it keeps coming back accounts for something 
though.

Original comment by jvdne...@gmail.com on 18 Aug 2009 at 8:42

[GoogleCodeExporter]

I am not specifically declaring this to be out of scope, but it's important to 
realize 
that this kind of functional programming stuff has never been our core focus.  
The 
main reason we have Predicate at all is just that it's hard to filter an 
iterator by 
hand, and a filter() library method needs something like that, so there it is. 
The 
main reason we have Function is that MapMaker needs it.

Original comment by kevin...@gmail.com on 18 Aug 2009 at 9:51

[GoogleCodeExporter]

(remember that "Accepted" != "promise that we will do it")

Original comment by kevin...@gmail.com on 17 Sep 2009 at 4:59

• Changed state: Accepted
• Added labels: post-1.0

[GoogleCodeExporter]

Original comment by kevin...@gmail.com on 17 Sep 2009 at 5:45

• Added labels: Milestone-Post1.0
• Removed labels: post-1.0

[GoogleCodeExporter]

Original comment by kevin...@gmail.com on 17 Sep 2009 at 5:57

• Added labels: Type-Enhancement

[GoogleCodeExporter]

This issue has been moved to the Guava project (keeping the same id number). 
Simply replace 'google-collections' with 'guava-libraries' in your address 
bar and it should take you there.

Original comment by kevinb@google.com on 5 Jan 2010 at 11:09

• Changed state: Moved