/*            Inheritance and Algebraic Data Types

   In this implementation of algebraic linked lists, I first drop polymorphism 
   so as to make the example as simple as possible.
*/

using System;


// The interface defines all operations that we wish to perform on the
// linked list ADT:

public interface list
{
   int length();  // length of list
   int product(); // product of all elements 
   int min(int ax);     // smallest element of list given ax as accumulator
   bool empty();  // is list empty?
   void print();  // prints list elements
   int car();     // head of list
   list cdr();    // tail of list
}

// There are two kinds of lists: the empty list and a structure with an
// int and an existing list.  We thus have two subtypes of list:

// In a conventional implementation of lists, you'll see code that
// always have to check if something is null: (if (null? l) ... or
// if (l==null) ..., but here, all that's avoided. All distinctions 
// between the two kinds of lists are now handled by inheritance.


class nil : list     // class for empty list
{
   public int length() { return 0; }
   public int product() { return 1; }
   public int min(int ax) { return ax; }  // end of tail-recursion
   public void print() { Console.Write("\n"); }
   public bool empty()  { return true; }
   public int car() {throw new Exception("no car for empty list");}
   public list cdr() {throw new Exception("find yourself a non-empty list!");}
} // nil


class cell : list   // class for non-empty list
{
  private int head;
  private list tail;   // note the type is list, not cell
  public cell(int h, list t)
    { head = h;  tail = t; }

  public int length() { return 1+tail.length(); } 
  public int product() { return head * tail.product(); }
  public int min(int ax)   // ax is for tail-recursion
    {
	if (head<ax) return tail.min(head); // head is new min
	else return tail.min(ax);
    }
  public bool empty() { return false; }
  public void print() { Console.Write(head+" ");  tail.print(); }
  public int car() { return head; }
  public list cdr() { return tail; }
} // cell


// You may complain that we need a new instance of nil each time we
// have to represent the empty list.  But that can be avoided by
// simply declaring a single static instance of nil that's shared by  
// all lists.

public class lists
{
  // shared static instance of nil:
  public static readonly list NIL = new nil();

  public static void Main()
  {
     list A = new cell(2,new cell(3,new cell(5,new cell(7,NIL))));
     Console.WriteLine(A.length());
     Console.WriteLine(A.product());
     Console.WriteLine(A.min(A.car()));
     A.print();
     // NIL.car();  // will throw uncaught exception
  } // main
}//lists

/* We can expand this example so as to have different kinds of cells,
   ones that contain data other than just integers
*/