java: libraries for immutable functional-style data structures

Question

This is very similar to another question (Functional Data Structures in Java) but the answers there are not particularly useful.

I need to use immutable versions of the standard Java collections (e.g. HashMap / TreeMap / ArrayList / LinkedList / HashSet / TreeSet). By "immutable" I mean immutable in the functional sense (e.g. purely functional data structures), where updating operations on the data structure do not change the original data, but instead return a new instance of the same kind of data structure. Also typically new and old instances of the data structure will share immutable data to be efficient in time and space.

From what I can tell my options include:

• Functional Java
• Scala
• Clojure

but I'm not sure whether any of these are particularly appealing to me. I have a few requirements/desirements:

• the collections in question should be usable directly in Java (with the appropriate libraries in the classpath). FJ would work for me; I'm not sure if I can use Scala's or Clojure's data structures in Java w/o having to use the compilers/interpreters from those languages and w/o having to write Scala or Clojure code.

• Core operations on lists/maps/sets should be possible w/o having to create function objects with confusing syntaxes (FJ looks slightly iffy)

• They should be efficient in time and space. I'm looking for a library which ideally has done some performance testing. FJ's TreeMap is based on a red-black tree, not sure how that rates.

• Documentation / tutorials should be good enough so someone can get started quickly using the data structures. FJ fails on that front.

Any suggestions?

Answer 1

Scala

You can call the methods of either language from methods in the other one

http://www.scala-lang.org/faq/4

Answer 2

It seems to me you already know what your options are, you just aren't happy with any of them. Here is my take on the three choices you've provided:

Functional Java - This one seems like the best fit for you. It fits all of your requirements except that you don't like the documentation. From my perspective the documentation looks basic, but serviceable. Their code snippets should get you up and running quickly. The learning curve seems almost non-existent which should help mitigate the lack of documentation. FYI, core Java's TreeMap is based on a Red-Black tree as well.

Scala - This is the choice I would make if I was in your shoes. You seem to not want to learn a new language, but Scala is a very easy transition from Java. You can write very java-like code at first, and slowly adopt more functional idioms. The Java <-> Scala interop is excellent in both directions as well.

Clojure - As much as I love Clojure, its tough to recommend in this particular instance due to the radically different syntax and steep learning curve for a java developer.