Efficient immutable data structures for Java

[joshsh]

If you look at the implementations of the hydra.lib.lists, hydra.lib.maps, and hydra.lib.sets primitives in Java, you will find that they achieve immutability through copying. For example, when you insert a key/value pair into a Map, the result is a new map which contains the pair, and also all of the original pairs which aren't shadowed by the new key. This is necessary because Hydra is functionally pure, and assumes that any reference to the original map is immutable.

However, this copying is very inefficient. It is common in Hydra to build collections while traversing a tree, exploring a graph, etc., which can be expected to make Hydra-Java much less space- and time-efficient at certain tasks than Hydra-Haskell. We need efficient List, Map, and Set implementations which support efficient random access / testing, but also efficient extension. One option I am aware of is Vavr, although I am wary of introducing that dependency. More likely, we will want to create our own ImmutableList, ImmutableMap and ImmutableSet implementations which extend List, Map, and Set, if there is nothing else out there.

This is an optimization which can wait until after Hydra 1.0.

[joshsh]

Note: other potential good fits are PCollections, JImmutable Collections, and Paguro.

All good projects, but all relatively unknown, which might introduce a little too much risk for a long-term dependency. Most likely, we will roll our own. We only need those three interfaces, with only two actual implementations if you consider that ImmutableSet can be derived from ImmutableMap.

[joshsh]

Note that this goes for Hydra-generated classes as well as built-in collection classes. For example, in operations involving types, it is common to pass a TypeContext which is modified throughout a series of branching recursive function calls. It will be worth exploring generating Java classes with support for efficient immutable operations, e.g. using shared-tail linked lists.