/* polymorphic linked list, second version.  The algebraic approach 

  This time, we will try to make polymorphism easier by taking advantage
of inheritance and dynamic dispatch.  But make no mistake: if a function
is not naturally polymorphic, there is no way to avoid writing different
procedures.  Algorithms don't grow on trees.

  Instead of using "object" as the generic type of cells, we define
  a sub class for each type of cell.

*/
using System;

interface list
{
   object CAR { get; }
   list CDR { get; }
   int length();
   object sum();
}

// sub classes for each kind of list:

class nil : list  //  class for empty list
{
   public object CAR { get { throw new Exception("nothing to get"); } }
   public list CDR { get { return null; } } // can also throw exception

   public int length() { return 0; }
   public object sum() { return null; }
}


class cell    // superclass for all non-nil lists
{
   protected list tail;  // head will be defined by subclasses
   public list CDR { get { return tail; } }
   public int length() { return 1 + tail.length(); } // automatic dispatch!
}

// note how the cell class serves a different purpose from the interface.
// It doesn't have to implement the interface.  We can also use an abstract
// class in place of an interface, but then we would not be able to 
// inherit any other classes.  Using interfaces gives us more flexibility.


class icell : cell, list // class for integer cells
{
   private int head;
   public icell(int x, list t) {head=x; tail=t;}
   public object CAR { get { return head; } }
   public object sum()
    {
       object s = tail.sum();
       if (s==null) s=0; // can't cast null to int
       return head + (int)s;
    }
} // icell

class dcell : cell, list // class for double cells
{
   private double head;
   public dcell(double x, list t) {head=x; tail=t;}
   public object CAR { get { return head; } }
   public object sum()
   {
       object s = tail.sum();
       if (s==null) s=0;  // can't cast null to double
       return head + (double)s;
   }
} // dcell

class scell : cell, list // class for string cells
{
  private string head;
  public scell(string x, list t) {head=x; tail=t;}
  public object CAR { get { return head; } }
  public object sum()
  {
     return head + " " + tail.sum(); // + forces autocast to string type.
  }
} // scell

public class list2
{
  static list NIL = new nil(); 
  public static void Main()
  {
    list A = new icell(2,new icell(4, new icell(6,NIL))); // note not null!
    list B = new scell("abc", new scell("def", new scell("ghi",NIL)));
    Console.WriteLine((int)A.sum());
    Console.WriteLine((string)B.sum());
  } // main
}


/*
    Although this program is longer, the code is more modular.  There
    was no need to use "is" to explicity test for types, since that's
    automatically handled by dynamic dispatch.  
*/