Higher-order collection methods

AugmentedIterable.java

public interface AugmentedIterable<T> extends Iterable<T> {

    // Apply function f to each element in the collection (in order), collecting
    // the results in a new collection, which is returned.
    <R> AugmentedIterable<R> map(Function1<R, T> f);

    // Apply function f to the seed value and the first element in the
    // collection, then apply f to the result and the second element in
    // the collection, then apply f to that result and the third element in
    // the collection, etc. returning the final computed result.
    // If the collection is empty, then return the seed value.
    <R> R foldLeft(Function2<R, R, T> f, R seed);

    // Apply function f to the last element in the collection and the seed
    // value, then apply f to the second-last element and the previous result,
    // then apply f to the third-last element and that result, etc.
    // returning the final computed result.
    // If the collection is empty, then return the seed value.
    <R> R foldRight(Function2<R, T, R> f, R seed);

    // Apply function f to each element in the collection (in order), and
    // collect the values returned from each f application, to be returned in
    // a new collection.
    <R> AugmentedIterable<R> flatMap(Function1<? extends Iterable<R>, T> f);

    // Return the elements of the this collection (in their original order)
    // that return true for the given predicate.
    AugmentedIterable<T> filter(Function1<Boolean, T> predicate);
}

Filter.java

public abstract class ImmutableList<T> implements AugmentedIterable<T> {

    /* ... previous method and subclass definitions ... */

    @Override
    public final ImmutableList<T> filter(Function1<Boolean, T> predicate) {
        ImmutableList<T> input = this;
        ImmutableList<T> output = nil();
        // This traversal constructs the output list by
        // prepending, yielding a list in reverse order.
        while (!input.isEmpty()) {
            if (predicate.evaluate(input.head())) {
                output = output.prepend(input.head());
            }
            input = input.tail();
        }
        // Use reverse to get back the original order.
        return output.reverse();
    }
}


public abstract class Option<T> implements AugmentedIterable<T> {

    /* ... previous method and subclass definitions ... */

    public final Option<T> filter(Function1<Boolean, T> predicate) {
        if (isDefined() && predicate.evaluate(get())) {
            return this;
        }
        return none();
    }
}

FilterTest.java

public class ImmutableListTest {

    /* ... previous test methods ... */

    @Test
    public void testFilter() throws Exception {
        ImmutableList<Integer> list = list(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
        Function1<Boolean, Integer> isEven = new Function1<Boolean, Integer>() {
            @Override
            public Boolean evaluate(final Function1<Boolean, Integer> self,
                                    final Integer i1) {
                return i1 % 2 == 0;
            }
        };
        
        assertEquals(list(2, 4, 6, 8, 10), list.filter(isEven));
    }
}

public class OptionTest {

    /* ... previous test methods ... */
    @Test
    public void testFilter() throws Exception {
        Option<Integer> a = some(2);
        Option<Integer> b = some(1);
        Option<Integer> c = none();

        Function1<Boolean, Integer> isEven = new Function1<Boolean, Integer>() {
            @Override
            public Boolean evaluate(final Function1<Boolean, Integer> self,
                                    final Integer i1) {
                return i1 % 2 == 0;
            }
        };

        // a is defined and even
        assertEquals(some(2), a.filter(isEven));
        // b is defined, but not even
        assertEquals(Option.<Integer>none(), b.filter(isEven));
        // c is undefined
        assertEquals(Option.<Integer>none(), c.filter(isEven));
    }
}

FlatMap.java

public abstract class ImmutableList<T> implements AugmentedIterable<T> {

    /* ... previous method and subclass definitions ... */

    public final <R> ImmutableList<R>
    flatMap(Function1<? extends Iterable<R>, T> f) {
        ImmutableList<T> input = this;
        ImmutableList<R> output = nil();
        while (!input.isEmpty()) {
            // Unlike with map(), we know that the return value
            // from f is itself iterable. So, we iterate and
            // accumulate those values.
            Iterable<R> rs = f.evaluate(input.head());
            for (R r : rs) {
                output = output.prepend(r);
            }
            input = input.tail();
        }
        return output.reverse();
    }
}

public abstract class Option<T> implements AugmentedIterable<T> {

    /* ... previous method and subclass definitions ... */
    public final <R> Option<R> flatMap(Function1<? extends Iterable<R>, T> f) {
        if (!isDefined()) {
            return none();
        }

        Iterable<? extends R> val = f.evaluate(get());
        Iterator<? extends R> iter = val.iterator();
        if (iter.hasNext()) {
            Option<R> result = option(iter.next());
            if (iter.hasNext()) {
                // Option.flatMap only works with functions that return at most
                // one element.
                throw new RuntimeException("Function passed to Option flatMap " +
                        "returns more than one element");
            }
            return result;
        }
        return none();
    }
}

FlatMapTest.java

public class ImmutableListTest {

    /* ... previous test methods ... */
    @Test
    public void testFlatMap() throws Exception {
        ImmutableList<Integer> list = list(1, 2, 3);

        // oneToN :: n -> [1..n]
        Function1<ImmutableList<Integer>, Integer> oneToN =
                new Function1<ImmutableList<Integer>, Integer>() {
                    @Override
                    public ImmutableList<Integer>
                    evaluate(final Function1<ImmutableList<Integer>, Integer> self,
                             final Integer i1) {
                        ImmutableList<Integer> list = ImmutableList.nil();
                        for (int i = i1; i >= 1; i--) {
                            list = list.prepend(i);
                        }
                        return list;
                    }
                };
        assertEquals(list(1, 1, 2, 1, 2, 3), list.flatMap(oneToN));
    }
}

public class OptionTest {

    /* ... previous test methods ... */

    @Test
    public void testFlatMap() throws Exception {
        Option<Integer> a = some(5);
        Option<Integer> b = none();
        Option<Integer> c = some(0);
        // safeDivide prevents divByZero errors by returning None
        Function2<Option<Integer>, Integer, Integer> safeDivide =
                new Function2<Option<Integer>, Integer, Integer>() {
                    @Override
                    public Option<Integer>
                    evaluate(final Function2<Option<Integer>, Integer, Integer> self,
                             final Integer i1, final Integer i2) {
                        if (i2 == 0) {
                            return none();
                        }
                        return some(i1 / i2);
                    }
                };
        // 10 / 5 returns 2
        assertEquals(some(2), a.flatMap(safeDivide.apply(10)));
        // 10 / none returns none
        assertEquals(Option.<Integer>none(), b.flatMap(safeDivide.apply(10)));
        // 10 / 0 returns none
        assertEquals(Option.<Integer>none(), c.flatMap(safeDivide.apply(10)));
    }
}

Fold.java

public abstract class ImmutableList<T> implements AugmentedIterable<T> {

    /* ... previous method and subclass definitions ... */

    @Override
    public final <R> R foldLeft(Function2<R, R, T> f, R seed) {
        ImmutableList<T> input = this;
        R output = seed;
        while (!input.isEmpty()) {
            output = f.evaluate(output, input.head());
            input = input.tail();
        }
        return output;
    }

    @Override
    public final <R> R foldRight(Function2<R, T, R> f, R seed) {
        // Reverse the list so that we can traverse from right to left
        // by traversing from left to right, effectively reducing the
        // problem to foldLeft.
        ImmutableList<T> input = this.reverse();
        R output = seed;
        while (!input.isEmpty()) {
            output = f.evaluate(input.head(), output);
            input = input.tail();
        }
        return output;
    }
}


public abstract class Option<T> implements AugmentedIterable<T> {
    @Override
    public final <R> R foldLeft(final Function2<R, R, T> f, final R seed) {
        return isDefined() ? f.evaluate(seed, get()) : seed;
    }

    @Override
    public final <R> R foldRight(final Function2<R, T, R> f, final R seed) {
        return isDefined() ? f.evaluate(get(), seed) : seed;
    }
}

FoldTest.java

public class ImmutableListTest {

    /* ... previous test methods ... */

    @Test
    public void testFold() {
        Function2<String, String, String> concat =
                new Function2<String, String, String>() {
                    @Override
                    public String evaluate(
                            final Function2<String, String, String> self,
                            final String i1, final String i2) {
                        return i1 + i2;
                    }
                };

        ImmutableList<String> list = list("a", "b", "c");
        assertEquals("dabc", list.foldLeft(concat, "d"));
        assertEquals("abcd", list.foldRight(concat, "d"));

        ImmutableList<String> emptyList = list();
        assertEquals("d", emptyList.foldLeft(concat, "d"));
        assertEquals("d", emptyList.foldRight(concat, "d"));
    }
}

public class OptionTest {

    /* ... previous test methods ... */

    @Test
    public void testFold() throws Exception {
        Function2<String, String, String> concat =
                new Function2<String, String, String>() {
                    @Override
                    public String evaluate(final Function2<String, String, String> self,
                                           final String i1, final String i2) {
                        return i1 + i2;
                    }
                };

        Option<String> a = some("a");
        assertEquals("ba", a.foldLeft(concat, "b"));
        assertEquals("ab", a.foldRight(concat, "b"));

        Option<String> b = none();
        assertEquals("b", b.foldLeft(concat, "b"));
        assertEquals("b", b.foldRight(concat, "b"));
    }
}

Map.java

public abstract class ImmutableList<T> implements AugmentedIterable<T> {

    /* ... previous method and subclass definitions ... */

    @Override
    public final <R> ImmutableList<R> map(Function1<R, T> f) {
        ImmutableList<T> input = this;
        ImmutableList<R> output = nil();
        // This traversal constructs the output list by
        // prepending, yielding a list in reverse order.
        while (!input.isEmpty()) {
            output = output.prepend(f.evaluate(input.head()));
            input = input.tail();
        }
        // Use reverse to get back the original order.
        return output.reverse();
    }
}

public abstract class Option<T> implements AugmentedIterable<T> {

    /* ... previous method and subclass definitions ... */

    public final <R> Option<R> map(Function1<R, T> f) {
        return isDefined() ? option(f.evaluate(get())) : Option.<R>none();
    }
}

MapTest.java

public class ImmutableListTest {

    /* ... previous test methods ... */

    @Test
    public void testMap() throws Exception {
        ImmutableList<Integer> list = list(1, 2, 3);
        Function1<Integer, Integer> dbl = new Function1<Integer, Integer>() {
            @Override
            public Integer evaluate(final Function1<Integer, Integer> self,
                                    final Integer i1) {
                return i1 * 2;
            }
        };
        ImmutableList<Integer> doubledList = list.map(dbl);
        assertEquals(list(2, 4, 6), doubledList);
    }
}

public class OptionTest {

    /* ... previous test methods ... */

    @Test
    public void testMap() throws Exception {
        Option<Integer> a = some(5);
        Option<Integer> b = none();
        Function1<Integer, Integer> dbl = new Function1<Integer, Integer>() {
            @Override
            public Integer evaluate(final Function1<Integer, Integer> self,
                                    final Integer i1) {
                return i1 * 2;
            }
        };
        assertEquals(some(10), a.map(dbl));
        assertEquals(Option.<Integer>none(), b.map(dbl));
    }
}