Created
April 18, 2012 22:02
-
-
Save msfroh/2416910 to your computer and use it in GitHub Desktop.
Higher-order collection methods
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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(); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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(); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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))); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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")); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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(); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment