4 5/17: Accumulators and Parameterized Data Definitions

The goal of this lab is to practice accumulator-based designs with objects and to start working with parameterized data definitions (often called “generics” in Java).

Accumulating knowledge

In class, we developed a straightforward approach to reversing a list using structural recursion. Unfortunately, that approach, since it involves a double recursion over the list, takes time proportional to the square of the size of the list. We then did much better by developing an equivalent accumulator-based designed that accumulated the elements we’d seen so far in reverse order. That code, which we developed in ISL, was:

;; Reverse the given list of integers

;; LoI -> LoI

(define (my-reverse lon)

(reverse/acc lon empty))

;; LoI LoI -> LoI

;; ACCUM: rev represents list of elements we've seen so far, in reverse order.

(define (reverse/acc lon rev)

(cond [(empty? lon) rev]

[(cons? lon)

(reverse/acc (rest lon)

(cons (first lon) rev))]))

Now we’d like to translate this idea over to Java.

Exercise 1. Develop a reverse method using an accumulator-based design in Java. You must support the original interface for reverse, namely that any LoI has a reverse method that accepts no inputs and produces the list in reverse order.

Once you’ve seen how to develop reverse, you can apply the same principles to design other accumulator-based methods.

Exercise 2. Develop a sum method using an accumulator-based design.

Exercise 3. Develop an append method using an accumulator-based design. The append method should consume one argument which is a LoI and append this list and the given list together.

Generalizing types

Yesterday we saw how to generalize the list of integers data definition to represent lists of any kind of elements.

Exercise 4. Develop a general List<X> data definition and recreate the methods from above.

You should notice that the sum method no longer type-checks. Why is that? For the moment, just comment out the sum method and proceed with the development of reverse and append. We’ll talk more about how to handle the sum issue in class.

Lists are the only thing that generalize. On today’s exam, you developed a data definition for binary trees of integers. Now try your hand at desigining a parameterized version of binary trees.

Exercise 5. Design a BT<X> data definition for binary trees where nodes contain data of type X.

Exercise 6. Design a height and size method for BT<X> that computes the height of a tree and the number of elements it contains, respectively.

Exercise 7. Design the mirror method for BT<X> that computes the mirror image of the binary tree.

Exercise 8. Using the Predicate<X> interface we studied in class, design an ormap method for binary trees that computes whether any element of the tree satisfies a given predicate. Design an analogous andmap method.

Exercise 9. Design a predicate on integers that produces true only for even numbers. Use this predicate to test your ormap and andmap designs from above.