I am trying to create a little functional programming library for Java (just to scratch my own itch). While defining the higher-order functions for List
s, Set
s and Map
s I have come across this problem: The functions that take a collection, and return a collection of same type have almost the same implementation, and yet have to be redefined for each of the data structure - List
s, Set
s, and Map
s.
For example, here is the implementation of map
function for List
s, and Set
s:
public static <A, B> List<B> map(
List<? extends A> xs,
Func1<? super A, ? extends B> transformer
) {
List<B> ys = new ArrayList<B>();
for(A a : xs) {
ys.add(transformer.apply(a));
}
return ys;
}
public static <A, B> Set<B> map(
Set<? extends A> xs,
Func1<? super A, ? extends B> transformer
) {
Set<B> ys = new HashSet<B>();
for(A a : xs) {
ys.add(transformer.apply(a));
}
return ys;
}
A filter
function:
public static <A> List<A> filter(
List<? extends A> xs,
Func1<? super A, Boolean> predicate
) {
List<A> ys = new ArrayList<A>();
for(A a : xs) {
if(predicate.apply(a)) {
ys.add(a);
}
}
return ys;
}
public static <A> Set<A> filter(
Set<? extends A> xs,
Func1<? super A, Boolean> predicate
) {
Set<A> ys = new HashSet<A>();
for(A a : xs) {
if(predicate.apply(a)) {
ys.add(a);
}
}
return ys;
}
As can be seen from this example, the bodies of the implementations for Set
and List
are almost the same.
There are lot many functions like map
and filter
in my library, and each of those is defined thrice for each type of collections I am interested in (i.e. List
, Set
, and Map
). This leads to a lot of code duplication, and code smell. I wanted to know whether there's some way in Java that would help me avoid all the code duplication.
Any help will be greatly appreciated. Thanks.
EDIT:
Func1
is an interface defined as:
interface Func1<A, B> {
public B apply(A a);
}
public static <A, B> List<B> map(
List<? extends A> xs,
Func1<? super A, ? extends B> transformer
) {
List<B> ys = new ArrayList<B>();
map(xy, transformer, ys);
return ys;
}
public static <A, B> Set<B> map(
Set<? extends A> xs,
Func1<? super A, ? extends B> transformer
) {
Set<B> ys = new HashSet<B>();
map(xy, transformer, ys);
return ys;
}
private static <A, B> map(
Collection<? extends A> xs,
Func1<? super A, ? extends B> transformer,
Iterable<B> ys
) {
for(A a : xs) {
ys.add(transformer.apply(a));
}
}
Job done.
Note, it's typical of Java APIs, to pass the mutable the collection in, rather than create a new one in the method. Personally, I'm not a fan of mutability at the collection level, but it's what we have to work with (in Java).
(I'm not keen on A
and B
as generic parameters with this sort of stuff.)
Or you could use a factory:
public static <A, B> List<B> map(
List<? extends A> xs,
Func1<? super A, ? extends B> transformer
) {
return map(xs, transformer, new CollectionFactory<B, List<B>>() {
public List<B> create() { return new ArrayList<B>(); }
});
}
public static <A, B> Set<B> map(
Set<? extends A> xs,
Func1<? super A, ? extends B> transformer
) {
return map(xs, transformer, new CollectionFactory<B, Set<B>>() {
public Set<B> create() { return new HashSet<B>(); }
});
}
private interface CollectionFactory<E, C extends Collection<E>> {
C create();
}
private static <A, B, C extends Collection<B>> C map(
Iterable<? extends A> xs,
Func1<? super A, ? extends B> transformer,
CollectionFactory<B, C> factory
) {
C ys = factory.create();
for(A a : xs) {
ys.add(transformer.apply(a));
}
return ys;
}
(If you can put up with the pointless verbosity of anonymous inner classes.)
If it wasn't for Collection
then you'd need to put some (ugly) adapter in.
For completeness (though not tested, could do with a few tweaks), an unpleasant solution using inheritance:
Set<String> strs = hashSets().map(things, formatter);
...
public static <E> Functions<E, Set<E>> hashSets() {
return new Functions<E, Set<E>>() {
protected Set<E> createCollections() {
return new HashSet<E>();
}
};
}
public abstract class Functions<E, C extends Collection<E>> {
protected abstract C createCollection();
public <S> C map(
Set<? extends S> xs,
Func1<? super S, ? extends E> transformer
) {
C ys = createCollection();
for(S a : xs) {
ys.add(transformer.apply(a));
}
return ys;
}
public <S> C filter(
List<? extends S> xs,
Func1<? super S, Boolean> predicate // Predicate<? super S> might be nicer!!
) {
C ys = createCollection();
for(A a : xs) {
if(predicate.apply(a)) {
ys.add(a);
}
}
return ys;
}
}
Java doesn't have higher-order polymorphism (aka higher-kinds) so this is not possible within the type system. Many Java programmers resort to XML and/or reflection (i.e. escape the type system) to address this deficiency.
Scala can deal with this and what you are describing is called a covariant functor. This rather fundamental data type (along with much more) has been implemented in the Scalaz library and includes implementations for java.util.*.
Further, there are many more covariant functors that are not collections and many more functors that are not covariant.
You may wish to google for "20 Intermediate Scala Exercises" if you wish to explore this particular concept further.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With