8 6/5: Array Lists
The goal of this lab is to practice designing methods for indexed, mutable data such as ArrayLists.
Simple functional methods on ArrayLists
There are basically two ways to design a method that operates on indexed data: either count up or count down:
Result methodA(ArrayList<T> as) { |
return methodAi(as, as.size()-1); |
} |
|
Result methodB(ArrayList<T> as) { |
return methodBi(as, 0); |
} |
|
Result methodAi(ArrayList<T> as, Integer i) { |
if (i.equals(-1)) { |
... |
} else { |
... as.get(i) ... methodAi(as, i-1) ... |
} |
} |
|
Result methodBi(ArrayList<T> as, Integer i) { |
if (i.equals(as.size())) { |
... |
} else { |
... as.get(i) ... methodBi(as, i+1) ... |
} |
} |
Exercise 1. Design a method Integer sum(ArrayList<Integer> is) that sums an array list of integers. Implement the method counting up and counting down.
Exercise 2. Design a method Integer prod(ArrayList<Integer> is) that computes the product of an array list of integers. Implement the method counting up and counting down.
Recall our interface for “combiner” functions:
interface Combiner<A,B> { |
// Combine an A and B into a B |
B combine(A a, B b); |
} |
Exercise 3. Design a method <A,B> B foldr(ArrayList<A> is, B base, Combiner<A,B> f) that computes the right fold of the given function and base over the array list, that is, this method should compute a result analogous to foldr from ISL. Should the method count up or down?
Exercise 4. Design a method <A,B> B foldl(ArrayList<A> is, B base, Combiner<A,B> f) that computes the left fold of the given function and base over the array list, that is, this method should compute a result analogous to foldl from ISL. Should the method count up or down?
Exercise 5. Re-implement prod and sum using your fold methods.
Recall the Predicate<T> interface we saw previously:
interface Predicate<T> { |
// Does this predicate hold for t? |
Boolean apply(T t); |
} |
Exercise 6. Design a method <T> Boolean ormap(ArrayList<T> is, Predicate<T> p) that computes whether any element of the list satisfies the given predicate. Implement the method counting up and counting down.
Exercise 7. Design a method <T> Integer find(ArrayList<T> is, Predicate<T> p) that computes the index of the first element that satisfies the predicate (or -1 if there’s no such element). Should the method count up or count down?
Exercise 8. Design a method <T> Boolean same(ArrayList<T> is, ArrayList<T> js) that determines whether the two given arrays are “the same”, meaning they have the same elements, in the same order. Implement the method counting up and counting down.
Exercise 9. Design a method <T> ArrayList<T> reverse(ArrayList<T> is) that computes the reverse of the given list. (This method should have no effect on is.)
Here is a data definition for pairs:
class Pair<X,Y> { |
Pair(X left, Y right) { |
this.left = left; |
this.right = right; |
} |
} |
Exercise 10. Design a method <T,V> ArrayList<Pair<T,V>> zip(ArrayList<T> is, ArrayList<V> js) that “zips” together an array list of Ts and an array list of Vs into an array list of pairs of Ts and Vs. You may assume the given lists are the same length.
Some imperative methods on ArrayLists
Now you’ll design a few methods that mutate their input list.
Exercise 11. Design a method <T> void reverseBang(ArrayList<T> is) that has the effect of reversing the given list.
Exercise 12. Design a method <T> void replaceBang(ArrayList<T> is, Predicate<T> p, T t) that has the effect of replacing every element that satisfies the predicate with the given value.
Here was our interface definition for functions:
// Represents a function [X -> Y] |
interface Fun<X,Y> { |
// Apply this function to argument x. |
Y apply(X x); |
} |
Exercise 13. Design a method <T> void updateBang(ArrayList<T> is, Fun<T,T> f) that has the effect of replacing every element with the result of applying the function to that element.