/* Sequences in Java */

public class seq
{
  static intseq cons (int car, intseq cdr)    // Syntactic Sugar
	{ return (new intseq(car,cdr)); }

  static int length(intseq S)         // returns length of S
        { if (S == null) return 0; else return (1+length(S.tail)); }

  static void printseq(intseq S)      // prints the sequence S 
    	{ if (S == null) System.out.println("");  // CR at end'
	    else
   	       { System.out.print(S.head + " ");
 	         printseq(S.tail);
               }
	}

  static intseq append(intseq A, intseq B)  // appends A and B
     	{ if (A == null) return B;   
  	    else { 
		   return cons(A.head, append(A.tail,B));
		 }
 	}

  static int min(intseq S)    // returns smallest integer in S
        { if (S == null) return 0;
	    else if (S.tail == null) return S.head;
	      else if (S.head >= S.tail.head)
		return min(S.tail);    // throw away first element
	else {                         // throw away second element
	       return min(cons(S.head,S.tail.tail));
	     }
	}

  // deletes ALL occurrences of x from S:
  static intseq delete(int x, intseq S)     // NEW!!!
        { if (S == null) return null;
            else if (S.head == x) return delete(x,S.tail);
	        else return cons(S.head,delete(x,S.tail));
        }

  public static void main(String args[])
   { intseq A, B, C, D;

   /* Keep in mind that 'cons(X,Y)' is really 'new intseq(X,Y)'. */

     A = cons(1, (cons (3, cons(5, (cons (7, null))))));
     B = cons(6, (cons (4, cons(2, (cons (9, (cons (3, null))))))));
     C = cons(0,A);

     System.out.println("the length of B is " + length(B));
     printseq(A);
     printseq(B);
     printseq(C);

     System.out.println("-----------");
     D = append(A,B);
     printseq(D);

     System.out.println("the min of B is " + min(B));

   }
  
}



/* Main class definition: */

class intseq  
{ int 	   head;
  intseq   tail;

  public intseq (int car, intseq cdr)    // constructor
     { head = car;  tail = cdr; }
}


/*  Inductive Definition of (integer) sequences: 

    Base Case:  'null' is a sequence
    Ind. Case:  if L is a sequence and h is an 'int',
	 	then  'new intseq(h,L)' is a sequence.




    FYI: Java is not as "algebraic" a language as Prolog.  There is nothing
    in Java to prevent a programmer from doing the following:
    
    A = cons(1,null);
    B = cons(2,A);
    A.tail = B;

    This will create a circular list.  This may be useful occasionally,
    but it's no longer a *finite* sequence.  It's not what we want.
    We can alleviate this problem somewhat by making head and tail
    *private* instead of public, and define two functions: geth() and
    gett() to return the head and tail respectively.  This will take
    away the ability to change the tail of a sequence (unless you also
    define settail() - and then you have the same problem again).  But
    even so the same error can still occur with methods defined
    *inside* the class definition of intseq.

    There's a really advanced programming language called ML that will
    allow you to define intseq's as follows:

          datatype intseq = null | cons of int*intseq;

    This will ensure that any "object" of type "intseq" can ONLY be
    null or the cons of previously so defined intseqs.  That is, the
    implicit part of the inductive definition "...and these are the
    ONLY sequences" is not enforced in Java.  It is up to the
    programmer to ensure that pointers don't point to places they
    shouldn't.  This gives the *advanced* Java programmer slightly
    more flexibility at the cost of mathematical clarity.  Fortunately,
    Java is much more "algebraic" than C and C++.  We make progress!

*/