Use delegation to write map/filter in Java

The problem

In Java, imagine you have a list of User objects, each encapsulates the user’s id, first name, last name and age. Then you want to call a web service UserService.deleteUsersByIds(List<Integer> userIds) to delete the users from your data store. It doesn’t sound too hard, does it? All you need to do is to transform you List<User> to List<Integer>. So you go ahead and write the following code:

List<Integer> ids = new ArrayList<Integer>(users.size());
for (User user : users) {
  ids.append(user.getId());
}

Then you go ahead and use your ids list, and everything is fine and dandy.

However, two minutes later, you find yourself having to provide another API method with a list of user’s names in String. So, again, you exercise your CSC101 skill:

List<String> names = new ArrayList<String>(users.size());
for (User user : users) {
  names.append(new StringBuilder(user.getFirstName()).append(" ").append("user.getLastName()));
}

Now, something else comes along and you need to write a piece of code that returns a list of names that belong to people who are under 21 years of age in the list…You get the idea. Well, things get boring pretty quickly.

As it turns out, these are two very important functions in functional programming: map and filter.

  • map(coll, f) “loops” over the collection, calls the function f on each element, and add the return of the f(element) to the return collection.
  • filter(coll, f) “loops” over the collection, calls f(element), and only add element to the return list when f(element) returns true

Use delegation for generic-ity

Now we take our first step in designing our generic map function:

<FromType, ToType> List<ToType> map(ArrayList<FromType> list) {
  List<ToType> retval = new ArrayList<ToType>(list.size());
  for (FromType item : list) {
    [...]
  }
  return retval;
}

What we left out in the above code snippet is how the input is mapped to the output. This is where delegates come in. Unfortunately, Java doesn’t have the language-level delegate. We need to design an interface for this delegate.

interface MapDelegate<FromType, ToType> {
  ToType map(FromType obj);
}

The delegate is parameterized (to provide more type safety) with FromType and ToType. FromType is the type of the objects in the original list, and ToType is the type of objects in the mapped list. Now we need to change our method signature to incorporate the delegate.

<FromType, ToType> List<ToType> map(ArrayList<FromType> list, MapDelegate<FromType, ToType> mapDelegate) {
  List<ToType> retval = new ArrayList<ToType>(list.size());
  for (FromType item : list) {
    retval.add(mapDelegate.map(item));
  }
  return retval;
}

Now the client code will look like this:

List<User> users = getUserListFromSomeWhere();
List<String> ids = map(users, new MapDelegate<User,String>() {
  public String map(User obj) {
    return new StringBuilder(user.getFirstName()).append(" ").append("user.getLastName()).toString();
  }
});

Similarly, we can write a filter function:

<T> List<T> filter(List<T> list, FilterDelegate<T> filterDelegate) {
  List<T> retval = new ArrayList<T>(list.size());
  for (T item : list) {
    if (filterDelegate.filter(item)
      retval.add(item);
  return retval;
}
interface FilterDelegate<T> {
  boolean filter(T item);
}

What about return value creation?

Use delegation, we can separate the parts of an algorithm in terms of their interfaces and leave the implementation to the caller. However, given the above filter and map methods, what if I don’t want the return type to be ArrayList? What if I want a LinkedList or a HashSet? Doesn’t the statement

  List<T> retval = new ArrayList<T>(list.size());

an implementation by itself?

Absolutely! For more flexibility, the “new” statement in the implementation body has to be delegated out as well. We introduce a ReturnDelegate interface:

interface ReturnDelegate<R extends Collection<?>> {
  R createReturnCollection();
}

and plug in the return delegate to the map method:

<FromType, ToType, R extends Collection<?>> R map(Collection<FromType> coll, MapDelegate<FromType, ToType> mapDelegate, ReturnDelegate<R> returnDelegate) {
  R retval = returnDelegate.createReturnCollection();
  for (FromType item : list) {
    retval.add(mapDelegate.map(item));
  }
  return retval;
}

Now the actual implementation has been completely separated. I know you can probably achieve flexibility without return delegate with the use of reflection, but on some systems (like GWT, which is what I’m working on and what this code is originally designed for), reflection is off limits.

Advertisements
Leave a comment

11 Comments

  1. bqlr

     /  March 1, 2010

    ><FromType, ToType, R extends Collection> R map(Collection coll, MapDelegate mapDelegate, ReturnDelegate returnDelegate)

    my god ,heavy header, it this script or xml?

    Reply
    • I understand what you’re saying. Java generics isn’t the most visually attractive, but until better type inferencing comes in, we kinda have no choice…

      Reply
  2. john

     /  March 3, 2010

    you should take a look at Google Collections

    Reply
    • Was just going to post exactly that: Google collections does what you want but more elegantly (still not nearly as neat as closures though).

      Reply
      • mastacode

         /  March 3, 2010

        And i was just going to post exactly the same 😉

  3. @john, @Sjoerd, @mastacode: thanks for the reply. I’m aware of the Google Collections API but this article is just an example and exercise of using delegation to implement something useful from scratch, particularly when you don’t want to pull in yet another dependency.

    Reply
  4. torvego

     /  March 3, 2010

    …or Collections from Apache Commons.

    Reply
  5. You’ll probably be interested in Functional Java http://functionaljava.org/ which does this but to a much higher level.

    Reply
  6. Kris Hoff

     /  March 4, 2010

    Need something like LINQ in Java guys. It is about time.

    Reply
  7. This is an awesome example of how good OO code should be written. Thanks!

    Reply
  8. I Liked the post. I love generics and reflection. They almost all the time eliminate the need for the boilerplate code.

    Thank you.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: