Cons.java

public class Cons<A> implements IList<A> {

    /**
     * リストの先頭要素
     */
    private A x;
    /**
     * リストの残りの要素
     */
    private IList<A> xs; // 型変数を忘れないように!

    public Cons(A x, IList<A> xs) {
        this.x = x;
        this.xs = xs;
    }

    public Cons<A> cons(A x) {
        return new Cons<A>(x, this);
    }

    public int length() {
        return 1 + this.xs.length();
    }

    @Override
    public String toString() {
        return this.x.toString() + " " + this.xs.toString();
    }
}

IList.java

public interface IList<A> {

    /**
     * リストの先頭に要素 a を追加する
     * @param a 追加する要素
     * @return リスト
     */
    public IList<A> cons(A x);

    /**
     * リストの要素数を返す
     * @return リストの要素数
     */
    public int length();
}

Main.java

public class Main {

    public static void main(String[] args) {
        // 型変数を忘れないように!
        IList<Integer> list = new Nil<Integer>().cons(4).cons(3).cons(2).cons(1);

        System.out.println(list);
        System.out.println(list.length());
    }
}

Nil.java

/**
* 空リスト
*/
public class Nil<A> implements IList<A> {

    public IList<A> cons(A a) {
        return new Cons(a, this);
    }

    public int length() {
        return 0;
    }

    @Override
    public String toString() {
        return "";
    }
}