Persistent data structures in Java

Question

Does anyone know a library or some at least some research on creating and using persistent data structures in Java? I don't refer to persistence as long term storage but persistence in terms of immutability (see Wikipedia entry).

I'm currently exploring different ways to model an api for persistent structures. Using builders seems to be a interesting solution:

// create persistent instance
Person p = Builder.create(Person.class)
             .withName("Joe")
             .withAddress(Builder.create(Address.class)
                 .withCity("paris")
                 .build())
              .build();

// change persistent instance, i.e. create a new one 
Person p2 = Builder.update(p).withName("Jack");

Person p3 = Builder.update(p)
              .withAddress(Builder.update(p.address())
                .withCity("Berlin")
                .build)
            .build();

But this still feels somewhat boilerplated. Any ideas?

Answer 1

I guess the obvious choices are:

o Switch to a transient data structure (builder) for the update. This is quite normal. StringBuilder for String manipulation for example. As your example.

Person p3 =
    Builder.update(p)
    .withAddress(
        Builder.update(p.address())
       .withCity("Berlin")
       .build()
    )
    .build();

o Always use persistent structures. Although there appears to be lots of copying, you should actually be sharing almost all state, so it is nowhere near as bad as it looks.

final Person p3 = p
    .withAddress(
        p.address().withCity("Berlin")
    );

o Explode the data structure into lots of variables and recombine with one huge and confusing constructor.

final Person p3 = Person.of(
    p.name(),
    Address.of(
       p.house(), p.street(), "Berlin", p.country()
    ),
    p.x(),
    p.y(),
    p.z()
 );

o Use call back interfaces to provide the new data. Even more boilerplate.

final Person p3 = Person.of(new PersonInfo(
    public String  name   () { return p.name(); )
    public Address address() { return Address.of(new AddressInfo() {
       private final Address a = p.address();
       public String house  () { return a.house()  ; }
       public String street () { return a.street() ; }
       public String city   () { return "Berlin"   ; }
       public String country() { return a.country(); }
    })),
    public Xxx     x() { return p.x(); }
    public Yyy     y() { return p.y(); }
    public Zzz     z() { return p.z(); }
 });

o Use nasty hacks to make fields transiently available to code.

final Person p3 = new PersonExploder(p) {{
    a = new AddressExploder(a) {{
        city = "Berlin";
    }}.get();
}}.get();

(Funnily enough I was just put down a copy of Purely Functional Data Structures by Chris Okasaki.)