interface Lambda { /** method containing the code for this lambda-expression mapping E to R */ R apply(E arg); } abstract class List { abstract R accept(ListVisitor v); ConsList cons(E elt) { return new ConsList(elt, this); } abstract List map (Lambda fun); abstract List catenate(List other); abstract String toStringHelp(); } interface ListVisitor { R forEmptyList(EmptyList host); R forConsList(ConsList host); } class EmptyList extends List { R accept(ListVisitor v) { return v.forEmptyList(this); } List map(Lambda fun) { return new EmptyList(); } List catenate(List other) { return other; } String toStringHelp() { return ""; } public String toString() { return "()"; } public boolean equals(Object other) { return getClass() == other.getClass(); } } class ConsList extends List { E first; List rest; ConsList(E f, List r) { first = f; rest = r; } R accept(ListVisitor v) { return v.forConsList(this); } List map(Lambda fun) { return rest.map(fun).cons(fun.apply(first)); } List catenate(List other) { return rest.catenate(other).cons(first); } String toStringHelp() { return " " + first + rest.toStringHelp(); } public String toString() { return "(" + first + rest.toStringHelp() + ")"; } public boolean equals(Object o) { return getClass() == o.getClass() && first.equals(((ConsList) o).first) && rest.equals(((ConsList) o).rest); } } class InsertVisitor implements ListVisitor> { E arg; InsertVisitor(E n) { arg = n; } public List forEmptyList(EmptyList host) { return new EmptyList().cons(arg); } public List forConsList(ConsList host) { if (arg.doubleValue() <= host.first.doubleValue()) return host.cons(arg); return host.rest.accept(this).cons(host.first); } } class MergeVisitor implements ListVisitor> { List other; MergeVisitor(List o) { other = o; } public List forEmptyList(EmptyList host) { return other; } public List forConsList(ConsList host) { return other.accept(new MergeHelpVisitor(host)); } } class MergeHelpVisitor implements ListVisitor> { ConsList other; MergeHelpVisitor(ConsList o) { other = o; } public List forEmptyList(EmptyList host) { return other; } public List forConsList(ConsList host) { E o1 = other.first; E h1 = host.first; List oRest = other.rest; List hRest = host.rest; if (o1.doubleValue() <= h1.doubleValue()) return oRest.accept(new MergeHelpVisitor(host)).cons(o1); else return hRest.accept(this).cons(h1); } }