Friday, December 08, 2006

An infinite list in Java

In Haskell you can define infinite lists by providing, for example, the arithmetical properties of a suite. Lazy evaluation means only the elements needed by the program are calculated. Now, I was looking at doing the same thing in Java, and there's not too much to it.
An infinite list is an Iterable over a generic type (called E in my code). The base class is abstract, and you need to provide the implementation of a getNext() method, that provides the next element in the list. The list is backed by an ArrayList, so that values are only calculated once. There is of course no size() method, but the size of the underlying array list tells you how many elements have been calculated. Note that each calculated value being stored in memory, you cannot go too far in a list with this system. But hey, we're playing here.

For example this is how you can implement the Fibonacci suite, using the code for InfiniteList here:

InfiniteList il=new InfiniteList(){
@Override
protected Integer getNext() {
switch (this.getData().size()){
case 0:return 1;
case 1:return 1;
default: return this.getData().get(this.getData().size()-1)+this.getData().get(this.getData().size()-2);
}
}
};

You then use the iterator() method to get all the results you need. Don't forget to stop at some stages. The getNext() method is called by the calculateNext() method on the base class:

private void calculateNext(){
E next=getNext();
data.add(next);
}

which in turn is called by the ensureCalculated method, that checks that we have the value at a particular index:

private void ensureCalculated(int index){
while (index>=data.size()){
calculateNext();
}
}

So the standard list get method becomes:

public E get(int index) {
if (index<0){
throw new IllegalArgumentException("index<0");
}
ensureCalculated(index);
return data.get(index);
}

You can then have the methods Haskell provide you, for example, take and map. Take returns a sublist made of the nth first elements of the list and map gives back another infinite list calculated from the first by applying a function to each element, as required. We can use the following interface:

public interface Mapper {
E2 map(E1 initial);
}

And the map method is:

public InfiniteList map(final Mapper mapper){
return new InfiniteList(){

@Override
protected E2 getNext() {
return mapper.map(InfiniteList.this.get(getData().size()));
}
};
}

We can also have another infinite list that is a filtered list from the original, using the same interface as above with the E2 generic type a boolean. Watch out, though: if the filter returns false all the time, a call to next() might never return...

The full code can be found here for the InfiniteList class, here for the Mapper interface. Sample code in the form of unit tests are here.

No comments: