From Accumulators to Java Loops

The code for this part of the lecture can be found here.

As our running example we will use the ALT class:

import java.util.ArrayList; 

class ALT<T> implements Traversal<T> { ArrayList<T> al; int 
first; 

  public ALT(ArrayList<T> al){ 
    this.al = al; 
    this.first = 0;
  } 

  // Used inside ALT only!
  private ALT(ArrayList<T> al, int first) { 
    this.al = al; 
    this.first = first; 
  } 

  // Traversal<T> methods 
  public T getFirst() { return al.get(this.first); } 
  public boolean isEmpty() { return this.first == al.size(); } 
  public Traversal<T> getRest() { return new ALT<T>(this.al, first + 1); }
 }
     

We will also use the class Student to help up us write some tests.


// to represent a student in our class 
class Student { 
  String name; 
  String lab; 
  int ssid; 

  public Student(String name, String lab, int ssid){ 
    this.name = name; 
    this.lab = lab; 
    this.ssid = ssid; 
  }

  public String toString(){  
    return new String(" Name : " + this.name +  ", " +
                      " Lab  : " + this.lab  +  ", " + 
                      " SSID : " + this.ssid ); 
  } 

}
  
      

And some examples to get the ball rolling. Some parts are elided here but you can see the full class definition here.


import java.util.ArrayList; 

class ALTTests { 
  // Students 
  Student skotthe = new Student("Theo", "A", 1234); 
  Student chadwick = new Student("Bryan", "B", 3456); 
  Student dimvar = new Student("Dimitris", "C", 7890); 
  Student chrdimo = new Student("Christos", "D", 1122); 
  Student mthomas = new Student("Mike", "A", 3344); 

  // ArrayLists 
  ArrayList<Student> al0; 
  ArrayList<Student> al1; 
  ArrayList<Student> al2;
  ArrayList<Student> al3;
  ArrayList<Student> al4;
  ArrayList<Student> al5;

  // ALTS
  ALT<Student> altMt = new ALT<Student>(al0);
  ALT<Student> alt1 = new ALT<Student>(al1); 
  ALT<Student> alt2 = new ALT<Student>(al2); 
  ALT<Student> alt3 = new ALT<Student>(al3); 
  ALT<Student> alt4 = new ALT<Student>(al4); 
  ALT<Student> alt5 = new ALT<Student>(al5); 


  public void resetData(){ 
  // elided
  } 

  public static void main(String[] args){ 
    ALTTests altt = new ALTTests(); 
    altt.resetData(); 
    altt.runTests();
 } 

  public void runTests() { 
    resetData(); 
    //Run
    System.out.println(" ==== Testing altMt ===="); 
    System.out.println("altMt = " + altMt.toString()); 
    System.out.println("altMt.isEmpty = " + altMt.isEmpty()); 

    System.out.println(" ==== Testing alt1 ===="); 
    System.out.println("alt1 = " + alt1.toString()); 
    System.out.println("alt1.isEmpty = " + alt1.isEmpty()); 
    System.out.println("alt1.getFirst = " + alt1.getFirst().toString()); 
    System.out.println("alt1.getRest = " + alt1.getRest().toString()); 

    System.out.println(" ==== Testing alt2 ===="); 
    System.out.println("alt2 = " + alt2.toString()); 
    System.out.println("alt2.isEmpty = " + alt2.isEmpty()); 
    System.out.println("alt2.getFirst = " + alt2.getFirst().toString()); 
    System.out.println("alt2.getRest = " + alt2.getRest().toString()); 

    System.out.println(" ==== Testing alt3 ===="); 
    System.out.println("alt3 = " + alt3.toString()); 
    System.out.println("alt3.isEmpty = " + alt3.isEmpty()); 
    System.out.println("alt3.getFirst = " + alt3.getFirst().toString()); 
    System.out.println("alt3.getRest = " + alt3.getRest().toString()); 

    System.out.println(" ==== Testing alt4 ===="); 
    System.out.println("alt4 = " + alt4.toString()); 
    System.out.println("alt4.isEmpty = " + alt4.isEmpty()); 
    System.out.println("alt4.getFirst = " + alt4.getFirst().toString()); 
    System.out.println("alt4.getRest = " + alt4.getRest().toString()); 

    System.out.println(" ==== Testing alt5 ===="); 
    System.out.println("alt5 = " + alt5.toString()); 
    System.out.println("alt5.isEmpty = " + alt5.isEmpty()); 
    System.out.println("alt5.getFirst = " + alt5.getFirst().toString()); 
    System.out.println("alt5.getRest = " + alt5.getRest().toString()); 
  } 
} 
      

Lets design a method with the name bigString that consumes a traversal of Students and returns all the names of the students concatenated as one big string. We want to implement this method using accumulators.

To assist us with our implementation we'll follow our Accumulator Template. For any method consuming a Traversal and implemented using accumulators we can use the following template as a guide.

<T> retType methodName(Traversal <T> tr, retType acc, ... ){
     if (tr.isEmpty())
       return acc;
     else
       return methodName(tr.getRest(),updateAcc(tr.getFirst(),acc, ... ));
}

Names in italics denote the parts of the template that vary. The ellipses (the three dots ...) denote extra arguments that we might need to pass to our method. These parts will be different according to the task your method is trying to accomplish.

Now that we have our template let's use it to develop bigString.

  // Concat all Student names in tr into one big string
  public String bigString(Traversal<Student> tr) { 
    return bigStringAcc(tr, ""); 
  } 

  // acc = Big string with all student names seen thus far
  private String bigStringAcc(Traversal<Student> tr, String acc){ 
    if (tr.isEmpty()) 
      return acc;
    else 
      return bigStringAcc(tr.getRest(), updateBigStringAcc(tr.getFirst(), acc)); 
  } 

  private String updateBigStringAcc(Student s, String acc){ 
    return acc.concat(s.name); 
  } 

Our bigString method consumes a Traversal of Students and returns a string holding all the names of students concatenated together. The method body returns the result of our accumulator method bigStringAcc. This means that bigStringAcc also returns a String. We pass our traversal object tr and the base value for our accumulator. Since bigStringAcc has String as a return type, our accumulator value will be of type String. This is based on our template.

Our bigStringAcc method consumes a Traversal of Students and an accumulator of type String. The body of our method is identical to our template except for the last statement. Our update method updateBigStringAcc consumes the first element of tr and our accumulator and returns a string. The body of our update method simply concatenates the students name to the current value of our accumulator.

One example is never enough. Let's define a new function orMap that will consume a Traversal, t, and an ISelect, pick, and produce a boolean. pick consumes an element of Traversal and returns a boolean. orMap logically or's the results returned by all the applications of pick on elements of tr. We want our implementation of orMap to be done using accumulators.

So in our ALT class we need to add the following method.

        public <T> boolean orMap(Traversal<T> tr, ISelect<T> pick){ 
          return orMapAcc(tr, pick, false); 
        }  
      

orMap takes two inputs; a Traversal,<T> tr and an ISelect,<T> pick. The body of our method calls orMapAcc, our accumulator implementation for orMap. We pass the traversal tr, our functional object pick, and the base value for our accumulator false.

How did we decide that our base value for our accumulator is false? If we look at our template we see that the type of the accumulator value is the same as the return type or our method. orMapAcc must have the same return type as orMap and orMap's return type is boolean. Therefore, according to our template the type of our accumulator acc should be boolean.

Now we need to design orMapAcc following our template.

   // using pick walk over tr calling pick on each element or-ing the results
  private  <T> boolean orMapAcc(Traversal<T> tr, ISelect<T> pick, boolean acc){ 
    if(tr.isEmpty())
      return acc; 
    else return orMapAcc(tr.getRest(),pick,updateOrMapAcc(tr.getFirst(), pick, acc)); 
  } 

The first usage of <T>, after the modifier private denotes that this is a generic method over the type variable T. Our retType is boolean as specified by orMap. We also need to pass to our function pick. We require pick since we need to call its select method on each element inside tr. This is an extra argument that we use in the place of the ellipses in our template.

The body of the method is the same except for the last statement. Our update method is called updateOrMapAcc and takes three arguments, the first element of our traversal tr.getFirst(), pick, and the accumulator acc. The update method is responsible for what needs to be done to each element and how to combine this answer with our accumulator.

Now we need to design updateOrMapAcc.

   private  <T>boolean updateOrMapAcc(T ele, ISelect<T> pick, boolean acc){ 
   	return pick.select(ele) || acc ; 
   } 

Our update method passes the element we got from tr to pick and combines the result with our accumulator using a logical or. This completes our implementation, using accumulators, for orMap.

As a last exmaple, let's define a new function filter that will consume a Traversal, t, and an ISelect, pick, and produce an ArrayList. pick consumes an element of Traversal and returns a boolean. filter excludes from the result all the elements of tr that don't satisfy pick. We want our implementation of filter to be done using accumulators.

So in our ALT class we need to add the following method.

    public ArrayList filter(Traversal tr, ISelect pick){ 
   	return filterAcc(tr, pick,new ArrayList()); 
    }
      

filter takes two inputs; a Traversal,<T> tr and an ISelect,<T> pick. The body of our method calls filterAcc, our accumulator implementation for filter. We pass the traversal tr, our functional object pick, and the base value for our accumulator ArrayList().

How did we decide that our base value for our accumulator is ArrayList()? If we look at our template we see that the type of the accumulator value is the same as the return type or our method. filterAcc must have the same return type as filter and filter's return type is ArrayList. Therefore, according to our template the type of our accumulator acc should be ArrayList.

Now we need to design filterAcc following our template.

    // using pick walk over tr calling pick and select only the elements that satisfy pick
    private ArrayList filterAcc(Traversal tr, ISelect pick, ArrayList acc){ 
    	if (tr.isEmpty())
	    return acc;
    	else
	   return filterAcc(tr.getRest(),pick,updateFilter(tr.getFirst(),pick,acc)); 
    }

The first usage of <T>, after the modifier private denotes that this is a generic method over the type variable T. Our retType is ArrayList as specified by filter. We also need to pass to our function pick. We require pick since we need to call its select method on each element inside tr. This is an extra argument that we use in the place of the ellipses in our template.

The body of the method is the same except for the last statement. Our update method is called updateFilterc and takes three arguments, the first element of our traversal tr.getFirst(), pick, and the accumulator acc. The update method is responsible for what needs to be done to each element and how to combine this answer with our accumulator.

Now we need to design updateFilter.

     private ArrayList updateFilter(T ele,ISelect pick,ArrayList acc){ 
     	if (pick.select(ele)){ 
     		 acc.add(ele);
    	  	return acc;}
        else 
      		return acc;
     } 
     

Our update method passes the element we got from tr to pick and combines the result with our accumulator using a logical or. This completes our implementation, using accumulators, for filter.

The Java language provides special syntax to deal with tasks of this kind. These constructs are called "loops" and come in two (main) flavours, the while and for loops.

While Loop

So let's take our previous example bigString and re-implement it using while loops. First, how does a while loop look like.

while(while-test){
    while-block
}

Informally, the while loops works as follows:

  1. Evaluate while-test.
    1. If while-test returns false jump to the end of while-block immediately after the closing curly brace.
    2. If while-test returns true then execute while-block once and go back to step 1.

So how would we use a while loop to implement bigString? Here's our code.

    public String bigStringWhile(Traversal tr){ 
     String acc= " "; // Base Value 
     while(!tr.isEmpty()){ 
      acc = updateBigStringAcc(tr.getFirst(), acc); 
      tr = tr.getRest(); 
     } 
     return acc; 
    } 

First we create a local variable acc for our accumulator and initialize its value to the accumulator's base value. Then while we still have students in our traversal to process we use updateBigStringAcc method to process the first student and update our accumulator. Then we assign to tr the remainder of our traversal, tr = tr.getRest();. We then loop back to the beginning of our while statement and repeat. Once we have processed all students in our traversal our while-test will return false and we will jump to the last statement in our method and that will return acc.