Assigned on Wednesday, 2/9.
Due on Friday, 2/18, by 4:55 PM.
Submission instructions: If you are working in a team, one member of the team should use hsp to turn in an entire directory called java_team that contains the file LazyList.java. Make sure that both team members are credited in program comments. For the individual assignment, each student should individually use hsp to submit a directory called java_indiv that contains the file Sorting.java.
Work through the Java introductory lab. This is intended to be easy and quick, and designed to be either a Java refresher or a warmup to get you started in Java if you are new to the language. You do not need to turn in anything from this lab, and is thus optional if your Java skills are current. There are some new Java 1.5 features demonstrated in here that you may wish to see.
Java is an object-oriented language and not a functional one, but there are aspects of Java that resemble functional programming. The Comparator interface is one such example.
(a) Create a file called Sorting.java. Copy and paste the following program into it:
import java.util.*;
class Sorting {
public static void main(String[] args) {
int listSize = 30;
int magnitude = 500;
Random rand = new Random(12345);
ArrayList<Integer> numbers = new ArrayList<Integer>(listSize);
for (int i=0; i < listSize; i++)
numbers.add(rand.nextInt() % magnitude);
Collections.sort(numbers);
for (Integer num : numbers)
System.out.print(num + " ");
System.out.println();
}
}
Look through the documentation for the class Collections. Specifically, find the method sort, and notice that there is another version of it that takes a Comparator object.
(b) Add a class to the top of the file called BackwardOrdering that implements the Comparator interface such that integers are ordered in reverse from their usual ordering. The following line of code should then sort the integers in reverse order:
Collections.sort(numbers, new BackwardOrdering());Add this line of code to the bottom of your program, then add a copy of the loop to print out the numbers again.
(c) Add a class to the top of the file called AlternatingOrdering that implements the Comparator interface such even that positive numbers are ordered as usual, but negative numbers are ordered in reverse. All positive numbers (and zero) are larger than all negative numbers. Add more code to the main method to sort the numbers by this wacky method using Collections.sort, then print out the results.
(d) How does this resemble functional programming? What's the connection? (Indicate your answer in program comments.)
Your task: Redo the last problem of the last Scheme assignment (lazy lists and the "Sieve of Eratosthenes") in Java. We will use the class Object to represent various kinds of lazy lists. Since Java does not support first-class functions, we'll use a similar technique as in the above problem. We will use an interface as above to contain a function:
interface LazyListFct {
LazyList f();
}
All implementations of LazyListFct will simply redefine f to be a particular function. For example, here is an excerpt from the infSeq function that you will write:
class LazyList {
...
public static LazyList infSeq(final int start) {
class InfSeqTail implements LazyListFct {
public LazyList f() {
return infSeq(start+1);
}
} // end of inner-class definition
// The code for infSeq goes here, using the above class
...
}
...
}
Whenever a particular function must be passed as a value, an instance of an implementation of LazyListFct is used.
The class you need to build, LazyList, is structured as:
class LazyList {
private Object head; // Head of this list, null if list is empty
private LazyListFct tail; // Function to compute tail of this list
// (if head is not null)
public LazyList() { // Default constructor for LazyList
head = null;
}
public LazyList(Object head, LazyListFct tail) {
// Another constructor
this.head = head;
this.tail = tail;
}
public static LazyList seq(final int start, final int finish) {
// Same definition as in previous assignment
}
public static LazyList infSeq(final int start) {
// Same definition as in previous assignment
}
public Object nth(int n) {
// Same definition as in previous assignment
// EXCEPT that it returns null if if n-th element does not exist
}
public void printN(int n) {
// Like firstN except that values are printed
// rather than formed into a list.
}
public static LazyList filterMultiples(final int factor,
final LazyList data) {
// Same definition as in previous assignment
}
public static LazyList primes() {
// Same definition as in previous assignment
}
public static void main(String[] args) {
// Create a lazy list and test that it works
LazyList primes = LazyList.primes();
primes.printN(15);
System.out.println(primes.Nth(20));
}
}
You could accomplish the same behavior in a slightly more confusing but considerably more condensed format using anonymous inner classes. After you get your code working, create another class called LazyListAnon that redoes all of the above with anonymous inner classes.
Many thanks to Prof. Charles Fischer at University of Wisconsin-Madison.