Tinkering around with java generics

[dtm]

And now for something totally geeky. Of interest only to those programmers whose programming interests encompass both java generics and functional languages that tend to represent lists as singly linked lists most of the time. This is just kind of wandering about, with no coherent theme or conclusion to the post.

First off, most functional-style languages implement lists on top of a basic data type called a pair (or, in lisp, a cons cell). So first let's do that:

public static class Pair<F,S> {
    private F _first;
    private S _second;
    public F getFirst() {
        return _first;
    }
    public S getSecond() {
        return _second;
    }
    public Pair(F first, S second) {
        _first = first;
        _second = second;
    }
}

I'm doing this code as a bunch of inner classes of one big PairListTest class, hence the static. Incidentally, I find that I'm constantly using Pair instead of tiny utility classes, and don't understand why Sun didn't add basic Pair and Tripple classes to java.util when they were adding generics.

In any case, what should it mean to have a list of type E? Well, it should be a Pair, and the first element should be an E and the second element should be either null or a list of type E. Let's write that:

public static class PList<E> extends Pair<E,PList<E>> {
    public PList(E elem) {
        super(elem, null);
    }
    public PList(E elem, PList<E> list) {
        super(elem, list);
    }
    public E head() {return getFirst();}
    public PList<E> tail() {return getSecond();}
} 

And that's somewhat nice. What can we do with it? Well, I'm pretty sure that nothing practical can be done, but doesn't this look fun?

public static <E> PList<E> append(PList<? extends E> first, PList<E> second)
{
    if (first == null) {
        return second;
    }
    return new PList<E>(first.head(),append(first.tail(),second));
}

There, it's a structure-preserving append! Just like lisp, or the ++ operator in Haskell. Really, though, that's unusable if the first argument has more than a few hundred elements, since it'll blow the stack. So, let's rewrite that iteratively. There may be some way to do that without adding structure-changing operations, (and without dumping it into a List<E>) but I don't know what it is. So first, assume I've added the obvious setFirst, setSecond, setHead, and setTail methods to Pair and PList:

public static <E> PList<E> append(PList<? extends E> first, PList<E> second)
{
    if (first == null) {
        return second;
    }
    PList<E> retval = new PList<E>(first.head(),null);
    PList<E> retLast = retval;
    PList<? extends E> it = first.tail();
    while (it != null) {
        PList<E> next = new PList<E>(it.head(),null);
        retLast.setTail(next);
        retLast = next;
        it = it.tail();
    }
    retLast.setTail(second);
    return retval;
}

Well, okay, but what else can be done with this? Well, now that I've given in and added structure-changing operations, how about nreverse?

/**
 * Reverses destructively in place.
 * Named after lisp's nreverse function.
 */
public static <E> PList<E> nreverse(PList<E> in)
{
    if (in == null) {return null;}
    PList<E> retval = in;
    PList<E> next = in.tail();
    in.setTail(null);
    while (next != null) {
        PList<E> prevRetval = retval;
        retval = next;
        next = next.tail();
        retval.setTail(prevRetval);
    }
    return retval;
}

This code still has some disadvantages that I'd like to get rid of.

For example, I'd like to say that you can use a PList<Cat> as a PList<Animal> (of course, you can't do this at all if you still have the set functions). Unfortunately, all my approaches to allow this came to naught. The closest I got was:

public static class PList<E> extends Pair<E,PList<? extends E>> {
    private PList(E elem, PList<? extends E> list) {
        super(elem, list);
    }
    public static<E> PList<? extends E> makeList(List<? extends E> inList) {
        PList<E> retval = null;
        for (ListIterator<? extends E> it = inList.listIterator(inList.size()); it.hasPrevious();)
        {
            retval = new PList<E>(it.previous(),retval);
        }
        return retval;
    }
    public static<E> PList<? extends E> makeList(E... eVals) {
        return makeList(Arrays.asList(eVals));
    }
    public static<E> PList<? extends E> cons(E h, PList<? extends E> t) {
        return new PList<E>(h,t);
    }
    public E head() {return getFirst();}
    public PList<? extends E> tail() {return getSecond();}
}

The private constructor is to keep me honest and to keep all my variables declared as PList<? extends E> instead of as PList<E>. I can now do:

public static <E> PList<? extends E> append(PList<? extends E> first, PList<? extends E> second)
{
    return revAppend(reverse(first),second);
}

public static <E> PList<? extends E> reverse(PList<? extends E> in) {
    return revAppend(in, null);
}

/**
 * Reverses first argument and appends second argument.
 * @param <E>
 * @param in
 * @param append
 * @return
 */
public static <E> PList<? extends E> revAppend(PList<? extends E> in, PList<? extends E> append) {
    PList<? extends E> retval = append;
    while (in != null) {
        retval = PList.cons(in.head(), retval);
        in = in.tail();
    }
    return retval;
}

And this works, in that I can now append a PList<? extends Dog> and a PList<? extends Cat> and assign the result to a variable of type PList<? extends Animal>, but I'd like to be able to declare my variables as Something<E> instead of the somewhat ugly PList<? extends E>. Unfortunately, I seem to be unable to do this in java.

Update: figured out a better way to do append in the ? extends E model.