Add a functional List type?

[xingyutangyuan]

The functional languages support List that can be "prepended" to functionally. That is, cons(1, [2, 3] results in [1, 2, 3].

I have a use case to frequently merge lists, so it's nice if I can do it faster than O(n).

[fluentfuture]

This is an interesting idea!

Coincidentally, I've run into a similar use case that may have benefited from an O(1) merged List.

It's not just for the Haskell-like cons(head, tail) style though, because I need to merge any arbitrary two lists, so it's more like concat(left, right).

This may be useful when for example to build a Guava RangeMap, where as soon as we find range overlapping, we split the range, and then merge the list of candidates that map to the same split-range. If we were using JDK List, we'd be doing O(n) merge to copy the elements; and then the next time another range overlap is detected, copy again.

Whereas if we have O(1) concatenation, the process of range split and overlapping detection will be more efficient. After we are done with the range split, we can then do a final O(n) transformation from the concatenation-optimized data structure to a standard List.

The API should be immutable, and we probably shouldn't name it List to avoid confusion with JDK (because it doesn't provide any JDK List operation such as random access). Maybe something like this?

@Immutable
public final class Chain<T> {
  public static <T> Chain<T> of(T element);
  public static <T> Chain<T> of(T element, T... remaining); 

  // O(1) operations to concat
  public static <T> Chain<T> concat(Chain<? extends T> left, Chain<? extends T> right);
  public Chain<T> concat(T element);

  // O(n) operations to consume the elements
  public Stream<T> stream();
  public <R> R collect(Collector<T, ?, R> collector);
}

One question is about hashCode/equals. It seems like we'll have to first collect the elements to a List before being to compare, which will be O(n). Can't seem to think of an efficient alternative (but maybe we can make it lazily-initialized to pay the cost only once).

[fluentfuture]

Just added a Sequence<T> class.

I ended up making it a subtype of List<T> because if I need to implement equals/hashCode, I'll need to use lazy initialization to create a List anyways. And once I have that List initialized, extending AbstractList<T> is easy enough.

Overall, user are expected to read from it still as a List. But they can concatenate it using O(1) operations.

[xingyutangyuan]

That looks great!

Question: Sequence doesn't seem to allow creating an empty Sequence? Any plan to support it?

[fluentfuture]

We could.

Though the way I imagine Sequence being used is as an intermediary type while you do frequent concatenations. After you are done, you'd either copy it to ImmutableList, or stream it to a terminal type.

For example, when trying to split ranges using collect(toImmutableRangeMap(BinaryOperator)), I can do:

List<Project> projects = ...;
ImmutableRangeMap<LocalDate, Sequence<Contributor>> dateRangeToContributorsList =
    biStream(projects)
        .mapKeys(Project::dateRange)
        .flatMapValues(project -> project.contributors().stream())
        .mapValues(Sequence::of)  // dateRange -> Sequence<Contributor>
        .collect(toImmutableRangeMap(Sequence::concat));

Wen you are ready to create a Sequence, it's never going to be empty.

Can you explain your use case that needs an empty Sequence?