I figured it was about time to try out java generics, so I decided to write some list processing primitives, and a Pair class that implements java.util.Collection. I intended to then use these to re-write my C3 implementation for Java more like the original Dylan it was adapted from.
There are a few articles around about implementing enumerators in languages without call/cc:
The reason to create Pair which implements java.util.Collection is that its really convenient to construct collections using cons in functions passed to fold.
My various enumerators all take Collection rather than Pair – since they are just as easy to implement that way. Notice that Collection.iterator() is all I need, so I decided not to require List. Also, its impossible for Pair to implement List efficiently.
The enumerators I have implemented so far are forEach(), foldLeft(), foldRight(), map()
Some other useful functions are all(), any(), and zip(), which were all used in implemented Pair.equals()
Of course java has the added the challenge of not being tail-recursive. foldRight() can’t be implemented recursively, since that is likely to cause a stack overflow. Instead, it uses ListIterator.hasPrevious() and ListIterator.previous(), after the collection is copied into an array list if neccessary. Obviously Java’s limited stack makes it a good idea to use foldRight().
I wanted to make array based variants zip, map, all and any, however problems with generics and arrays have made that impossible so far. Thats a shame, because it makes Pair.equals() fairly in-efficient.