5 5/22: Visitors
The goal of this lab is to practice designing visitors and adding the visitor pattern to inductively defined data.
Visiting data
The visitor pattern is a design technique that decouples data from functions. Once a data definition implements the visitor pattern, it allows new computations to be designed without the need to change the original definition. This is particularly important for parametric data definitions, since we can design typespecific visitors, overcoming the inability to add typespecific methods.
In this lab, you’ll practice adding the visitor pattern to various data definitions and writing computations as visitors.
Visiting lists
We saw in class the following data definition for parametric lists with the visitor pattern:
// Represents a computation over a list of X, producing an R. 
interface ListVisitor<X,R> { 
R visitEmpty(); 
R visitCons(X first, List<X> rest); 
} 

// Represents a list of X 
interface List<X> { 
// Accept visitor and compute. 
<R> R accept(ListVisitor<X,R> v); 
} 

class Empty<X> implements List<X> { 
Empty() {} 

public <R> R accept(ListVisitor<X,R> v) { 
return v.visitEmpty(); 
} 
} 

class Cons<X> implements List<X> { 
X first; 
List<X> rest; 
Cons(X first, List<X> rest) { 
this.first = first; 
this.rest = rest; 
} 

public <R> R accept(ListVisitor<X,R> v) { 
return v.visitCons(this.first, this.rest); 
} 
} 
To get started, let’s construct some simple visitors.
Exercise 1. Develop an implementation of ListVisitor<String,Integer> that computes the aggregate length of a list of strings.
Exercise 2. Develop an implementation of ListVisitor<String,Boolean> that computes whether a list of strings has an element "Boston".
Exercise 3. Develop an implementation of ListVisitor<String,String> that concatenates a list of strings together.
Exercise 4. Develop an implementation of ListVisitor<Integer,Boolean> that computes whether a list of integers has an element greater than 50.
Now let’s do some more sophisticated ones:
Exercise 5. Develop an implementation of ListVisitor<String,Boolean> that computes whether a list of strings has a given element.
Exercise 6. Develop an implementation of ListVisitor<Integer,Boolean> that computes whether a list of integers has an element greater than a given number.
Now for some even more sophisticated ones (these may involve writing helper visitors):
Exercise 7. Develop an implementation of ListVisitor<Integer,Integer> that computes the largest number in a nonempty list of integers.
Exercise 8. Develop an implementation of ListVisitor<String,String> that computes the shortest string in a nonempty list of strings.
Exercise 9. Develop an implementation of ListVisitor<Integer,Integer> that computes a number closest to a given number in a nonempty list of integers.
Visiting the tree of life
Now you should try your hand at developing visitors for other kinds of data. Revisit your solution to “The Tree of Life” problem from Lab 2.
Exercise 10. Implement the visitor pattern for your representation of life scenarios.
Exercise 11. Redevelop your solutions to exercise 1014 as visitors.
Exercise 12. Redevelop your solutions to exercise 16 and 17 as visitors that produce List<String>s.