Home > other >  How do I make my own generic functional list implementation in Java behave covariantly?
How do I make my own generic functional list implementation in Java behave covariantly?

Time:04-28

I am implementing my own linked list in Java mainly as an attempt to learnt the syntax. I have some experience in Scala, and am trying to implement a functional, immutable linked list. I'm having trouble understanding how to make a covariant concatenation method. I want to be able to concatenate (append) a List<Sub> with (to) a List<Super>.

public abstract List<T> {
    public abstract T head();
    public abstract List<T> tail();
    public abstract boolean isEmpty();
    // ... more methods
    public List<T> concat(List<? extends T> that) {
        if (this.isEmpty()) return (List<T>) that; // Gross
        else return new Cons<>(this.head(), this.tail().concat(that));
    }
}
public class Cons<T> extends List<T> {
    private final T head;
    private final List<T> tail;
    public boolean isEmpty() {return false;}
    public Cons(T head, List<T> tail) {this.head = head; this.tail = tail;}
    public T head() {return head;}
    public List<T> tail() {return tail;}
}
public class Nil<T> extends List<T> {
    public T head() {throw new NoSuchElementException();}
    public List<T> tail() {throw new NoSuchElementException();}
    public boolean isEmpty() {return true;}
}

I seem to only be able to do this by explicitly casting the list of subtypes to a list of supertypes which seems ugly. I'm essentially trying to mimic Scala's List[ T] covariance formalism. Cheers.

CodePudding user response:

As far as Java is concerned, a List<Subclass> isn't a List<Superclass>, and there's no way to tell it otherwise. Neither covariance nor contravariance is supported.

I can think of a few options here:

  1. Declare concat as returning List<? extends T>, rather than promising that it will return exactly List<T>.
  2. Do what you're doing — you know that, since your List class is immutable, it's safe to reinterpret a List<Subclass> as a List<Superclass>, so you can just cast it, plus an appropriate @SuppressWarnings annotation with a comment. (You'll probably want to centralize this in a private upcast method.)
  3. Declare Cons.tail as having type List<? extends T>, and whenever you need to convert from List<? extends Superclass> to List<Superclass>, you can do so by destructuring and reconstructing — creating a new Cons<Superclass> or Nil<Superclass> with the same fields. (The reason to declare Cons.tail as List<? extends T> is so that you don't need to copy the whole list over, but just the first cons.) (As with #2, you'll probably want to centralize this in a private upcast method, which Nil and Cons can each implement appropriately.)
  • Related