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 type-specific visitors, overcoming the inability to add type-specific 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 non-empty list of integers.

Exercise 8. Develop an implementation of ListVisitor<String,String> that computes the shortest string in a non-empty list of strings.

Exercise 9. Develop an implementation of ListVisitor<Integer,Integer> that computes a number closest to a given number in a non-empty 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 10-14 as visitors.

Exercise 12. Re-develop your solutions to exercise 16 and 17 as visitors that produce List<String>s.