Proper API for Java List

Java Collection Framework is quite old. First appeared in Java 1.2 and since then it changed not so much. It reflects OO-concepts as they were understood by the end of 20th century.

Since then many things changed and new understanding grew of what is actually needed from List, Set, Map, etc. API's. Much more often we're using immutable collections and many of us realize that we need completely different API's from one provided with standard JDK classes.

This article is dedicated to Lists, so I propose to discuss how ideal API for immutable Java List implementation should look like.

From my experience I've tried to prepare version of the API which should be more convenient to use:

public interface List<E> {
    /**
     * Return first element from list.
     * 
     * @return First element wrapped into {@link Option} if element is present or {@link Option#empty()} otherwise
     */
    Option<E> first();

    /**
     * Return first {@code N} elements from the list. If there are less elements than requested, then avalable
     * elements returned.
     * @param n
     *        Number of elements to return.
     *        
     * @return New list with at most requested number of elements
     */
    List<E> first(final int n);

    /**
     * Return last element from list.
     *
     * @return Last element wrapped into {@link Option} if element is present or {@link Option#empty()} otherwise
     */
    Option<E> last();

    /**
     * Return list which contains elements from current list followed by elements from list provided as parameter.
     * 
     * @param other
     *        List to append
     *        
     * @return List with elements from current list followed by elements from {@code other} list
     */
    List<E> append(final List<E> other);

    /**
     * Return list which contains elements from list provided as parameter followed by elements of current list.
     * 
     * @param other
     *        List to append to
     *        
     * @return List with elements from {@code other} list followed by elements from current list
     */
    List<E> prepend(final List<E> other);

    /**
     * Return list consisting of elements obtained from elements of current list with applied 
     * transformation function.
     * 
     * @param mapper
     *        Transformation function
     *        
     * @return New list with transformed elements
     */
    <R> List<R> map(final FN1<R, E> mapper);

    /**
     * Return list consisting of elements obtained from elements of current list with applied 
     * transformation function. Unlike {@link #map(FN1)} this method passes index of element
     * along with element to transformation function.
     *
     * @param mapper
     *        Transformation function
     *        
     * @return New list with transformed elements
     */
    <R> List<R> mapN(final FN2<R, Integer, E> mapper);

    /**
     * Applies specified consumer to elements of current list.
     * 
     * @param consumer
     *        Consumer for elements
     *        
     * @return Current list  
     */
    List<E> apply(final Consumer<E> consumer);

    /**
     * Applies specified consumer to elements of current list. 
     * Unlike {@link #apply(Consumer)} element index is passed along with element to consumer.
     * 
     * @param consumer
     *        Consumer for elements
     *        
     * @return Current list
     */
    List<E> applyN(final BiConsumer<Integer, E> consumer);

    /**
     * Create {@link Stream} from list elements.
     * 
     * @return Created stream
     */
    Stream<E> stream();

    /**
     * Return list size.
     * 
     * @return number of elements in list
     */
    int size();

    /**
     * Create new list which will hold the same elements but sorted according to 
     * provided comparator.
     * 
     * @param comparator
     *        Element comparator
     *        
     * @return Sorted list
     */
    List<E> sort(final Comparator<E> comparator);

    /**
     * Create new list which will hold only elements which satisfy provided predicate.
     * 
     * @param predicate
     *        Predicate to apply to elements
     * 
     * @return List of elements for which predicate returned {@code true}
     */
    List<E> filter(final Predicate<E> predicate);

    /**
     * Split current list into two using provided predicate. Result is a pair of lists. Left element of pair
     * contains list with elements evaluated to {@code false} by predicate. Right element of pair contains
     * list with elements evaluated to {@code true} by predicate.
     * 
     * @param predicate
     *        Predicate to apply to elements
     * 
     * @return Pair of lists with results 
     */
    Pair<List<E>, List<E>> splitBy(final Predicate<E> predicate);
}

Beside listed above API's there should be factory methods and Collector implementation which should enable convenient interaction of Stream API, but that part is more or less clear.

I'd be happy to get feedback on the List API proposed above and get any comments/ideas/suggestions/considerations in regard to it.

Comments

[michelemauro]

The original Java improvement project was Apache Commons Collections, and then of course Google Guava; both however never went as far as trying to redesign the Collections classes.

Have you checked out any of the many functional programming libraries out there? for example, Vavr and its List interface.

Or, going up in abstraction, Arrow-kt's NonEmptyList or even Scala's Seq.

You may find there some good new ideas, and a validation of your approach.

I wasn't able to find any JSR on the topic, so if you build up something interesting, there may be space for that.

[Sergiy Yevtushenko]

Thanks for the suggestion.

In my practice I've used Apache Commons and Guava. I've also looked into several other collections implementations, in particular Efficient Immutable/Persistent Collections for Java, GS Collections (now Eclipse Collections) and The Capsule Hash Trie Collections Library. Last one lacks List, but contains efficient implementations of Set and Map.

Also, I did read several articles which compare different implementations. One of them shows that GS Collections significantly more efficient in regard to memory and performance than Scala implementation. Sorry, have no link on that article handy.

Unfortunately most of mentioned above implementations do not try to rethink Java Collections interfaces completely.

The idea is to prepare API convenient for everyday use, rather than based on any theoretical considerations or paradigms.

Most inspiration for the API above I've obtained from Kotlin and some extension functions written by my colleagues for one of the projects I've recently worked on. As far as I can tell, this API covers vast majority of use cases I see in code.

One note: I think that java.util.List (as well as other collections) API stopped changing because of addition of stream() method. Streams are really powerful and convenient, so most (if not all) use cases can be covered with them. There are two drawbacks though:

• bridge to Streams caused stall in JCF API evolution (recent addition of factory methods basically changes nothing in List/Set/Map API's)
• there is some extra verbosity which pollutes code with unnecessary noise (.stream()...collect()).

[michelemauro]

Cool, didn't know about the Capsule library. Oh, and the Scala library is not optimized for primitive type efficiency like the GS one, so the benchmark result is not surprising 😁

Is your idea about introducing a better API, a more explicit (and probably better) performance footprint, or are you aiming at both with one stone?

[Sergiy Yevtushenko]

I've decided to start with API and implement it in very simple and straightforward way. Later I'm going to write better performing implementation while keeping API intact. Trying to do both things together is not the best approach since changes in API will be much harder to adopt and maintain.

[Sergiy Yevtushenko]

As for JSR: there is another idea I'm considering to submit to JCP. The idea is to implement support for variadic templates for Java. While working on Reactive Toolbox Core I've found that in many places such a functionality would significantly simplify code.

[Sergiy Yevtushenko]

One addition to the API:

    /**
     * Create new list which contains same elements reordered using given source of random numbers.
     *
     * @param random
     *        Random number source
     *
     * @return Shuffled list
     */
    List<E> shuffle(final Random random);