Semester 2 Week 1 (Defining your own recursive data structures (Lists))

1. Watch video about Week 8 number 1

2. Type in some simple expressions at the Hope prompt >: like:

   (1,2);
   (1,'a');
   [1,2];
   [1,2,1];
   [1+1,1,1];
   "dog";
   [[1,2],[1],[3]];
   

   Notice the types of the results.

3. Make up expressions of type:

   num
   char
   list(num)
   list(char)
   list(list(char))
   num X char
   num X char X num
   

4. Try out the length function in Hope on igor: Create a file in your home directory called ggg.hop containing:

   length: list(alpha) -> num;   ! length is a function which take a list and returns a number
   
   length(nil) <= 0;             !the length of the empty list is zero  
   length(x::m) <= 1+length(m);  ! length of the list whose head is x and tail is m
                                 ! is one more than the length of m
   
   length [1,2,3,1];
   

   Then type

   hope -f ggg.hop
   

   This will output

   >> 4 : num
   

   because that is the length of the list [1,2,3,1]. Use hope to work out the length of the following lists:

   [1,1,1,1,1]
   ['a','b']
   ["hello","goodbye"]
   [[],[1],[1],[1]];
   

   What is the type of each of the four lists above?

5. Watch video about Week 8 number 2
6. Watch video about Week 8 number 3

7. Copy the Java Programs in week8 on to your machine. Compile them and run test. Change test.java to print out some different lists.

   public abstract class seblist  <T>
   {
           public  abstract boolean isnil();
   	
   	public String toString()
   	{
   	  return "[" + commasBetween() + "]";
   	
   	}
     	 
           public abstract String commasBetween();
   	
   }
   
   
   
   public class sebnil <T> extends seblist <T>
   {
   	
   	public boolean isnil()
           {return true;
   	}
   
   	 
   	public String commasBetween()
           { return "";}
   	 
   }
   
   
   public class sebcons <T> extends seblist <T>
   {
   	T h;
   	seblist <T> t;
   
   	public sebcons(T o1, seblist  <T> m1)
   	{h=o1;t=m1;}
   
   	
           public boolean isnil()
           {return false;}
   
   	public String commasBetween()
           { if (t.isnil()) return h.toString();
             else return h.toString() +","+ t.commasBetween();}
   	 
          
   }
   
   class test
   {
   
   	public static void main (String []args)
   	{
   	
   		System.out.println(new sebcons(1,new sebcons(2,new sebnil())));	
   	
   	}
   
   }
   

8. Add the length method to seblist. You will have to add an abstract method int length() to seblist and a method int length() in sebnil and sebcons classes.
9. Write a program for testing your length method.

10. Define head and tail methods.
11. Try the Hope function for appending two lists:

    append: list(alpha) X list(alpha) -> list(alpha);
    append (nil,m) <=  m;   
    append (x::k,m) <= x::append(k,m);
    

12. Try the Hope function elementAt:

    elementAt: list(alpha) X num -> alpha;
    elementAt(0,x::m) <= x;
    elementAt(n+1,x::m) <= elementAt(n,m);
    

13. 1. Add the seblist append(seblist m) method to seblist. You will have to add an abstract method seblist append(seblist m) to seblist and a method seblist append(seblist m) in sebnil and sebcons classes.

    2. Add the Object elementAt(int n) method to seblist. You will have to add an abstract method Object elementAt(int n) to seblist and a method Object elementAt(int n) in sebnil and sebcons classes.

    3. Write a program for testing your append method.

    Solutions

14. (Easy Assignment) Add the following method to your generic lists classes:

    reverse:list(alpha) -> list(alpha);
    reverse(nil) <= nil;
    reverse(x::m) <= append(reverse(m),x::nil);
    

15. (Hard Assignment) Implement the following in Java as static methods:

    type string ==list(char);
    
    insert: string # list(string) -> list(string);
    insert (s,nil) <= s::nil;
    insert (s,y::m) <= if (s<y)
                       then s::(y::m)
    		   else y::insert(s,m);
    
    
    sort: list(string) -> list(string);
    sort(nil) <= nil;
    sort(x::m) <= insert(x,sort(m));
    

    Hint:

    static seblist <String> insert (String x, seblist <String> m) 
    
    static seblist <String> sort (seblist <String> m)