JEP 431: Sequenced Collections | Hacker News Reader

JEP 431: Sequenced Collections

openjdk.org

141 pointsludovicianul50 comments

I like JEPs such as this one. They show a strength of the current Java platform development community. We see multiple people spending significant thoughts and effort on what looks like a small feature. Which when implemented aims to feel so natural as if it was always there and no longer worth thinking about. Which in the makes so many people happier and more productive.

Oracle employs some pretty serious experts in language semantics to formally explore the implications of proposed changes. Most other languages just chuck things in.

I really admire Stuart Marks and his work, talks and writing. His work in Java APIs are much more approachable for laypersons like me who will be quick to pounce on various suggestions, problems and feature requests.

But I find his responses very well thought out and reasoned even though I personally may not like the outcome I can always see that the choice he made is perhaps the least worst option. This is no mean feat for a language still trying to evolve, even rapidly, after 25 years of cruft. This is unlike Brian Goetz’s work in Valhalla etc where you need more expertise to make meaningful suggestions.

Needless to say, very happy with this JEP. My only wish is make these updates come sooner but perhaps you need time to prepare and reason about new stuff instead of adding every little feature that may seem useful at first glance.

JEP 431: Sequenced Collections feels like it is inspired by Clojure's Seq interface / abstraction:

https://clojure.org/reference/sequences

Sequenced Collections: "Introduce new interfaces to represent collections with a defined encounter order. Each such collection has a well-defined first element, second element, and so forth, up to the last element. It also provides uniform APIs for accessing its first and last elements, and for processing its elements in reverse order."

Clojure Seq: "Clojure uses the ISeq interface to allow many data structures to provide access to their elements as sequences. The seq function yields an implementation of ISeq appropriate to the collection. Seqs differ from iterators in that they are persistent and immutable, not stateful cursors into a collection. As such, they are useful for much more than foreach - functions can consume and produce seqs, they are thread safe, they can share structure etc."

Or Smalltalk collections, or Lisp streams, or ML sequences,...

These ideas are quite old, the main issue has been the decades that have taken to finally reach mainstream.

The "optional" write methods look like awful design choices. If my method needs a writable sequenced collection I have no way to express that. I just need to hope that you give me one or you will get exceptions.

Why not break it into two interfaces? One for immutable and one with the mutable operations so that this is naturally expressible and checked by the type system?

It's how all Java collection interfaces work have worked since forever. They probably don't bother introducing new super-interfaces because Java code is never going to migrate from List etc.

But here we are, introducing new super-interfaces. Why not do it properly?

> It's how all Java collection interfaces work have worked since forever.

And it’s been an issue since forever, and this is specifically introducing new super-interfaces, so why miss the opportunity again?

Because developers are lazy and most will never migrate unless forced to.

1. It's been forever, and because of that:

2. People are never going to migrate from List, and so we:

3. Must do the same exact thing again and again, to ensure:

4. That people are never going to migrate from List

What if your method needs an empty collection, you'd have no way to express that. Or it needs a collection with even or odd number of elements depending on value of the first element.

At some point you have to stop playing with types and start coding.

This is an odd comment on a JEP for introducing more super types.

Parent comment is right: throwing an exception is surprising behavior and the interface’s design breaks the Liskov substitution principle.

You are right, but that is throwing the baby out with the bathwater. There is a limit to what can reasonably be expressed in a type system but that doesn't meant we should just give up. Moving a group of methods that just throw a NotImplementedError to a different interface so that you can talk about then seems fairly low effort and high value.

To statically analyze whether you receive an empty collection or not, you need dependent types, a thing which Java does not have, and will not have in foreseeable future.

To tell mutable and immutable collections apart, you just need two separate interfaces, a feature available in Java for decades, and an approach widely and routinely used everywhere in the language.

> To tell mutable and immutable collections apart, you just need two separate interfaces, a feature available in Java for decades, and an approach widely and routinely used everywhere in the language.

Part of the problem might be that Java's existing interfaces for collections don't have that split. `List`, `Set`, and `Map` already declare mutators, and they're used pervasively.

On the other hand, the Java folks clearly recognize that mutability is the wrong default for modern programming languages, so why double down on the mistakes of the past? They might argue that it makes more sense to follow established patterns than it does to create new ones, because it creates less friction for Java developers.

This is discussed in the following section:

> Add, put, and UnsupportedOperationException

Because when dealing with mutability, you usually want to specify which of two parties can mutate: none (immutable collection), only the producer (read-only interface), only the consumer (transfer of ownership), or both (mutable collection). E.g. a read-only interface does not tell a receiver whether or not it is safe to store in a field. So to do it "properly" either you multiply the number of interfaces by four, or complicate the type system to track ownership. Either way, the price for that feature is high, and it's not yet clear at this point whether the benefits are worth it.

Not every solution to every problem is worth it. Sometimes it's best to do nothing and spend the time on more worthwhile things, and perhaps a cheaper solution would present itself in the future.

IIRC Ceylon did this. It was very cool, especially with union and intersection types. They didn't use the standard java collection interfaces though. Too bad the language didn't take off.

Scala had a separate hierarchy of collections as well IIRC (and their entire collection thing seemed like a much better design than what Java did, admittedly with years of learning from Java's mistakes)

This is how it already has been in Java. It’s explained in an ancient Design FAQ document: https://docs.oracle.com/javase/8/docs/technotes/guides/colle...

I guess that's another change which is much more hard to implement properly. I'd like to see it done though.

At first glance, one might think Java already has collection types with defined encounter order - List (defined iteration order based on insertion order) and SortedSet/SortedMap (defined iteration order based on elements implementing the Comparable interface).

Reading more carefully, the proposal aims to lift the sequenced type higher up the hierarchy, so client code doesn't need to code to specific implementations.

So far, operations available on collection types are influenced by the implementation. So what happens if I call the proposed addFirst() on an ArrayList, rather than a LinkedList? For the former case, I doubt all the elements will get shifted up by one, so would it create a new underlying array?

(Edit: of course it would, the underlying array is recreated for resize operations already. But it would involve a slow array copy operation for what may be a common case operation). I guess my point here is, if you lift operations into a common super-type some of those operations may have implementation challenges for some subtypes.

(Edit 2: turns out it's already possible to insert an element at the head of an ArrayList using add(0, foo) so there's no change to supported methods, just an abstraction of existing APIs, as far as I can tell).

List lacks simple methods to access the head and tail. There are multiple times I wanted to get the tail element but had to do two calls (get size and get(size-1)). Having first()/last() methods would make it easy and more readable.

Doesn't java libs have a deq - a double-ended queue?

Yes, Java has java.util.Deque [1]. The purpose of this JEP is to add a more generic interface over the ordered collection types, which all have slightly different names for these operations.

[1] https://docs.oracle.com/en/java/javase/17/docs/api/java.base...

On the other hand the way the interfaces are layered is not ideal, because the implications of e.g. `removeFirst` and `removeLast` for an arraylist are very different from a linked list.

Or getLast on an arraylist (or doubly linked list) versus singly linked.

Nit: "tail" usually means "everything except the head", not "last element". I got a little confused there for a moment reading your comment.

Just signifies how good default method has revolutionized Java.

I think the benefits of this change for everyday development will far outweigh the complaints of language purists.

This is long overdue, and brilliant and well thought out work. But I can't help but feel like this is shoehorning a useful concept into a primitive type system that only knows inheritance as an abstraction. This sort of thing would be dead simple with Impl in Rust or Trait in Scala.

Doesn't this break every existing implementation of List/Deque/SortedSet, as now every implementation is missing the new interface methods?

So suddenly updating from Java N to Java N+1 will no longer compile your code.

This is solved by default methods in the interfaces.

They did acknowledge

> Introducing new methods high in the inheritance hierarchy runs the risk of clashes over obvious method names such as reversed and getFirst.

> We will analyze a large corpus of Java code in order to assess these risks.

Heh, so Hejlsberg was right, except they didn't go far enough (in C#, unlike Java, methods in classes aren't overridable by default and all overrides must be explicit - but implementing interfaces can be implicit, so this case can still cause quiet breakage).

How does JVM handle this at runtime if you don't recompile, though? In CLR, on IL level, interface implementations and overrides both explicitly designate the original method they override/implement - so even if an already-compiled class has a method with the same name and signature as the newly added interface method, it wouldn't be considered an implementation of that method until you recompile the class against the new interface. But in JVM, isn't it handled by name at runtime as well?

Forcing the use of something like @Override wouldn't have mattered because dispatch is dynamic -- it would only trigger a compilation error when recompiling from source. At runtime, if the methods have a different (and incompatible) return type then the original method would be called because the JVM does allow overloads that differ by return types, but the Java language doesn't, so already-compiled code would work as before, but it wouldn't compile from source (that's a source incompatibility, which is not as important in Java as binary compatibility). If the methods do have a matching signature to the default ones, then they will be called when the interface method is invoked, as overrides of the default methods. If, additionally, their behaviour is not one that conforms to the new interface's specification, that could be a problem. That's why a corpus analysis is needed, to see how frequently such methods were added in subclasses.

Since Java 8, there are default interface method implementations: https://docs.oracle.com/javase/tutorial/java/IandI/defaultme... . You can add any method to interface in backward-compatible way if you also define default implementation.

Java 8 introduced default method, exactly to cover cases like this. Presumably custom implementation would result in exception.

In addition to this, Java should eliminate unordered collections entirely and alias them to their ordered equivalents; for example, HashMap -> LinkedHashMap, HashSet -> LinkedHashSet. See [0].

[0]: https://publicobject.com/2016/02/08/linkedhashmap-is-always-...

That link claims the performance impact is negligible, but doesn't provide any benchmarks.

I find it hilarious that, after all these years, Java is still not adhering to the Interface Segregation principle - working with _small_ interfaces should be a thing. Having SequencedCollection inherit Collection goes against that.

On a larger scale, I think Java's support for inheritance of interfaces was a mistake from the start.

Inheritance of implementations is much worse %)

The industry at large has agreed that what is bad is inheritance of implementation, even hip languages like Rust support inheritance of interfaces, so Java isn't wrong there.

And naturally the whole COM like OO ABIs also support it.

Good point. We should use it mush much more sparingly then. ;)

Oh good, a chance to rant about one of my pet peeves. Sorted sets and maps are really useful for all sorts of things, but in Java, they are very much second-class citizens. This JEP touches on a few ways in which they lack lustre. But take a look at even creating them in the first place!

Firstly, assume we have a string lying around:

    String string = "mississippi";

Let's create some unsorted collections, from a literal (ish) expression, collecting a stream to a set, and collecting a stream to a map:

    Set<Integer> literal = Set.of(1, 2, 3);

    Set<Integer> collected = string.chars().boxed()
                                   .collect(Collectors.toSet());

    Map<Integer, Character> map = IntStream.range(0, string.length()).boxed()
                                           .collect(Collectors.toMap(Function.identity(),
                                                                     string::charAt));

Pretty easy.

Now if we want them to be sorted:

    SortedSet<Integer> literal = new TreeSet<>(Set.of(1, 2, 3));

    SortedSet<Integer> collected = string.chars().boxed()
                                         .collect(Collectors.toCollection(TreeSet::new));

    SortedMap<Integer, Character> map = IntStream.range(0, string.length()).boxed()
                                                 .collect(Collectors.toMap(Function.identity(),
                                                                           string::charAt,
                                                                           (a, b) -> { throw new UnsupportedOperationException(); },
                                                                           TreeMap::new));

Firstly, there is no SortedSet.of, so we have to explicitly wrap a literal set in a concrete implementation of SortedSet; as well as being a little less pretty, this means there's no chance for the JDK to use efficient specialised implementations of small constant sets, as it can for unsorted sets, and lists. Secondly, there is no toSortedSet collector, so we have to use the generic collection collector, again with a concrete implementation of SortedSet. Thirdly, there is no toSortedMap collector, so we have to use the generic toMap collector which again takes a concrete map implementation, but also requires us to handle key collisions ourself; this last point is particularly bad, because it is impossible to write a handler which is as good as the one used by the default toMap, because the handler doesn't get to see the colliding key!

What if we want them to be sorted in reverse?

    SortedSet<Integer> literal = new TreeSet<>(Comparator.reverseOrder());
    literal.addAll(Set.of(1, 2, 3));

    SortedSet<Integer> collected = string.chars().boxed()
                                         .collect(Collectors.toCollection(() -> new TreeSet<>(Comparator.reverseOrder())));

    SortedMap<Integer, Character> map = IntStream.range(0, string.length()).boxed()
                                                 .collect(Collectors.toMap(Function.identity(),
                                                                           string::charAt,
                                                                           (a, b) -> { throw new UnsupportedOperationException(); },
                                                                           () -> new TreeMap<>(Comparator.reverseOrder())));

Where we use a collector, we have to expand the map implementation constructor method reference to a lambda, so we can pass in a comparator; mildly annoying but not too bad. But for the literal, there is no constructor which takes both a comparator and elements, so we have to create the set with the comparator, and then add the elements! It becomes impossible to do this in a single expression, or to use an immutable collection, and it's several times the volume of code as the unsorted case.

If you want to write the reverse sorted literal as an expression, you can do this:

    SortedSet<Integer> literal = Stream.of(1, 2, 3)
                                       .collect(Collectors.toCollection(() -> new TreeSet<>(Comparator.reverseOrder())));

Which is still embarrassing.

How does C# handle this?

It doesn't. It has ICollection<T>, which is a collection of known finite length, and IList<T>, which adds the requirement that the items can be accessed via their ordinal index, thus implicitly defining the encounter order as well.

It's probably the Blub paradox speaking, but I haven't felt the need for an ISequencedCollection<T> in C#.

ICollection also already has many of the convenience methods from this JEP, like .First() and .Last()

Long overdue!

Reply on news.ycombinator.com