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?