//
//
//

public class List {
    int head;
    List tail;

    public List(int i,List tail){head = i; this.tail = tail;}

    public static int head(List l){return l.head;}
    public static List tail(List l){return l.tail;}

    public static int length(List l){
	if (l == null) return 0;
	else return 1 + length(tail(l));
    }

    public static int sum(List l){
	if (l == null) return 0;
	else return head(l) + sum(tail(l));
    }

    public static boolean exists(int e,List l){
	return l != null && (head(l) == e || exists(e,tail(l)));
    }

    public static List reverse(List l){
	if (l == null) return null;
	else return reverse(l,null);
    }

    private static List reverse(List l1,List l2){
	if (l1 == null) return l2;
	else return reverse(tail(l1),new List(head(l1),l2));
    }				

    private static List append(List l1,List l2){
	if (l1 == null) return l2;
	else return new List(head(l1),append(tail(l1),l2));
    }			    

    private static List delete(int e,List l){
	if (l == null) return null;
	else if (e == head(l)) return delete(e,tail(l));
	else return new List(head(l),delete(e,tail(l)));
    }

    private static int count(int e,List l){
	if (l == null) return 0;
	else if (head(l) == e) return 1 + count(e,tail(l));
	else return count(e,tail(l));
    }

    private static boolean equal(List l1,List l2){
	return (l1 == null && l2 == null) ||
	       (l1 != null && l2 != null && 
		head(l1) == head(l2) && equal(tail(l1),tail(l2)));
    }

    private static int nth(int n,List l){
	if (n == 0) return head(l);
	else return nth(n-1,tail(l));
    }

    public static List insert(int e,List l){
	if (l == null) return new List(e,null);
	else if (e < head(l)) return new List(e,l);
	else return new List(head(l),insert(e,tail(l)));
    }

    
    public String toString(){return "[" + toString(this) + "]";}

    private String toString(List l){
	if (l == null) return "";
	else if (tail(l) == null) return "" + head(l);
	else return head(l) +","+ toString(tail(l));
    }

    public static void main(String[] args) {
	List l1 = new List(7,new List(6,new List(5,new List(4,new List(3,null)))));
	List l2 = new List(9,new List(8,new List(7,new List(8,null))));

	System.out.println("1l = "+ l1);
	System.out.println("length("+ l1 +") = "+ length(l1));
	System.out.println("sum(" + l1 +") = "+ sum(l1));
	System.out.println("exists(4,"+ l1 +") "+ exists(4,l1));
	System.out.println("exists(-4,"+ l1 +") "+ exists(-4,l1));
	System.out.println("reverse("+ l1 +") = "+ reverse(l1));
	System.out.println("append("+ l1 +","+ l2 +" = "+ append(l1,l2));
	System.out.println("delete("+ 8 +","+ l2 +") = "+ delete(8,l2));
	System.out.println("count("+ 7 +","+ append(l2,l1) +") = "+ count(7,append(l2,l1)));
	System.out.println(equal(l1,l2));
	System.out.println(nth(3,l1));
	List l3 = insert(4,insert(3,insert(9,insert(4,insert(1,insert(8,null))))));
	System.out.println(l3);
    }
}
//
// code the following
//
//  - delete(e,l)   delivers a new list with e deleted from l  
//  - insert(e,l)   delivers a new list with e inserted in order into l
//  - count(e,l)    delivers the number of times e occurs in l
//  - nth(n,l)      delivers the nth element of the list l
//  - equal(l1,l2)  delivers true if lists l1 and l2 are equal
//  - append(l1,l2) delivers a new list with l2 appended to the end of l1
//