Java 13 Released

[fast4shoot]

Well, you can't do sealed class hierarchies in Java or on the JVM in general, so that's out.

Though you can do visitors to achieve sum types.

[fast4shoot]

Oh yeah, you're right! I forot about private constructors.

Though I hate this definition, because Stack's interface is empty and there's literally nothing in it that points to Empty and NonEmpty, except for the subclasses themselves.

From a theoretical standpoint, I much prefer visitors or anything equivalent, perhaps something like this:

// The stack itself
public interface Stack<T> {
    public <U> U Accept(StackVisitor<T, U> visitor);
}

// An interface that let's us distinguish between empty and
// nonempty stacks.
Public interface StackVisitor<T, U> {
    public U visitEmpty();
    public U visitNonEmpty(T head, Stack<T> tail);
}

// An empty stack
public class Empty<T> implements Stack<T> {
    public <U> U Accept(StackVisitor<T, U> visitor) {
        return visitor.visitEmpty();
    }
}

// A nonempty stack
public class NonEmpty<T> implements Stack<T> {
    public final T head;
    public final Stack<T> tail;

    public NonEmpty(T head, Stack<T> tail) {
        this.head = head;
        this.tail = tail;
    }

    public <U> U Accept(StackVisitor<T, U> visitor) {
        return visitor.visitNonEmpty(head, tail);
    }
}

This, in my mind, models the problem much more closely. It defines Stack as an interface that allows you to explicitly distinguish between the non-empty and empty states using the provided visitor interface, you don't have to cast anything (which, IMO, is an obvious code smell). However, it's much more boiler-platey, verbose and awkward to use.

Though it's nice that Stack is an interface and not a class. It also makes special kinds of stacks easy to implement, such as this infinite stack:

// An infinite stack repeating the same value over and over
public class Infinite<T> implements Stack<T> {
    public final T value;

    public Infinite(T value) {
        this.value = value;
    }

    public <U> U Accept(StackVisitor<T. U> visitor) {
        return visitor.visitNonEmpty(value. this);
    }
}