Functional list library for generic java

By: on July 18, 2005

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.



  1. tonyg says:

    … and that’s pretty inefficient.

    Yes, it is. Matthew’s earlier post about generics and arrays mentioned that parts of the standard library are copying objects willy-nilly; I wonder how imperative-language apologists reconcile the two ideas “our standard library copies a lot” and “functional programming languages copy a lot and are thus inefficient” with the statement “imperative languages are more efficient than functional languages”?

  2. tonyg says:

    ((I accidentally deleted a bunch of comments I didn’t mean to delete today, so I’m having to repost them manually:))

    Ray Pereda wrote:

    Suppose I have two list of 1 million items. I can make a third list which is the union of the other two without making a copy. A mutation oriented list will typically make a copy somewhere along the line. Functional list are so intuitive, I don’t understand why they are not more popular. It took Java to make garbage collection go main stream. I am looking for an problem where there are many lists which have common sublists. Please send email to my name all one word at yahoo if you know of such a problem.

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>