ArrayDeque should implement Deque interface

I really like that kotlin 1.3.70 added the ArrayDeque class. However I’m surprised that it didn’t also add a Deque interface. I always considered using interfaces instead of implementations as a good practice and kotlin seemed to follow this for collections. I mean kotlin even goes so far that the standard library decides on the list implementation you get.
In addition this would make interfacing with platform specific libraries far easier then now we can just wrapp the platform specific deque inside of a kotlin deque.

Is there any good reason not to provide such an interface in kotlin?

7 Likes

We haven’t found use cases so far that require such kind of interop. In our study, most usages of Deque were in some internal code that implemented some algorithm requiring queue/stack data structures.

We do not, however, exclude the possibility of introducing such (Mutable)Deque interface later, provided that we’ll find convincing applications for it.

In this particular case interop means that it may be that in cases where a multiplatform Deque interface is needed, this can not be met by the ArrayDeque class because it wasn’t declared to implement it. Basically, if such an interface doesn’t exist, it is not possible to use it from an interface perspective.

I don’t think this is a good reason. This cannot explain why we do not define the interface Stack and Queue and let ArrayDeque implement them. I believe that Stack and Queue are widely used data structures. And I cannot understand why defining the interfaces Stack and Queue has lower priority than implementing ArrayDeque.

So what are these cases in particular?

https://android.googlesource.com/platform/frameworks/support/+/refs/heads/androidx-master-dev/compose/compose-runtime/src/commonMain/kotlin/androidx/compose/Stack.kt

I tend to use a Deque when I need a FIFO queue. There are plenty of cases where this would be used in multi-platform code, including message queues. The reasons for using Deque rather than ArrayDeque are the general reasons why one may want to use interfaces instead of classes in interface definitions (analogous to List vs MutableList vs ArrayList). The problem with a virtual type ArrayDeque that decays to the java version on the jvm is that if this type doesn’t provide the interfaces and I want/need interfaces I cannot actually use the kotlin.ArrayDeque provided because its common definition does not declare it to implement the Deque interface.

Another reason to provide the interface now compared to later is the oportunity cost. Right now it costs nothing, but adding it later will require all kotlin libraries using ArrayDeque to uprgrade their public API to use Deque instead.

Most usages we’ve found so far are not in public API, so we don’t expect this cost to be high.
From the standard library development perspective it looks the opposite: not adding the interface now and adding it later is possible in a binary compatible way and gives an opportunity to design this interface better.

All these cases seem to encapsulate a deque and provide more domain specific public API. This is what makes the situation with deque different from the one with lists and other collections, and what makes it tolerable to defer the introduction of the interface.

On JVM and on the other platforms Kotlin’s ArrayDeque implements MutableList interface and all its supertypes. What other interfaces do you mean? java.util.Deque?

Yes, the interface I mean is java.util.Deque. I have to say though that the Java Deque interface is far from clean.

As I mentioned in the “checked exceptions” thread, I love interfaces for good API design. So I fully agree with @Wasabi375.

But sadly most newly designed interfaces like java.util.Deque are just a mess.

  • they are too big (too many functions to implement)
  • they extend lots of parent interfaces (even more functions to implement)

Good examples are closeable and iterable<T>

SUGGESTION:

Language team, it is great that Kolins’ classes should be as small as possible.
Therefore the extensions exist.

So please define lots of small specific interfaces and apply them to the Kotlin datastructures.

interface Iterable<T> { iteraor<T> } 
interface Writeable { empty }
interface Clearable extends Writeable { clear() }
interface Keyfetcher<K,V> { get(K):V }
interface MapRead<K,V> extends Keyfetcher
interface MapWrite<K,V> extends Writeable { put(K, V), replace ... }
interface Map<K,V> implements MapRead<K,V>, MapWrite<K,V>, Clearable
interface List implements Clearable ...
interface Cache implements Keyfetcher ...

So a Map can be used as Cache,
a ReadonlyMap will not implement WriteInterfaces

With that background, the design of new data structures will me more uniform, more easy to implement (just the expected functions). So all Caches will use Keyfetcher<K,V> and the function will be get(K):V

4 Likes

For FIFOs, what I would prefer is a clean, focused Queue interface that could express and enforce that I am using the structure as a queue and nothing else.
Just MutableCollection + ‘peek’ and ‘removeFirst’

MutableList would of course inherit it.

1 Like

You must mean MutableDeque, since an immutable Deque is just a List.

So the question is whether to have ArrayDeque : MutableDeque : MutableList or just ArrayDeque : MutableList

I can’t seem to imagine a realistic need for MutableDeque, really. “using interfaces instead of implementations” is important for passing things in an out, but List or MutableList is the interface you should use for that in all the scenarios I can imagine. (And thank you so much, JetBrains, for having ArrayDeque implement List!)

“using interfaces instead of implementations” for private fields is reasonable when you really don’t care how they’re implemented, but that’s a really small thing, and I’ve never seen an ArrayDeque used in Java where the implementation wasn’t important (i.e., where a LinkedList would be just as good). Also remember that MutableList already has add(0,E) and removeAt(0) – it’s bigger than a deque already.

I think JB’s decision to wait and see if a compelling use case pops up, so that maybe they can make sure the MutableDeque interface they come up with is appropriate for that use case, is practical and wise.

1 Like

A queue is by definition mutable.