I'm very keen on building a generic data-structure much like the Ent. Currently I've build a rough JAVA implementation that has all the nice properties.

The following API has been implemented:

• new-list(key, value) -> list
• insert-after(list, key, value) -> list
• insert-before(list, key, value) -> list
• get(list, key) -> value
• remove(list, key) -> list
• diff(list1, list2) -> list
• union(list1, list2) -> list
• split(list, key) -> (list1, list2)

Every operation creates a fresh new list without destroying the old one (it is a confluently persistent data-structure).

Every operation runs O(log(N)) except for diff and union. However, diff and union do have the so called BLOCK distance complexity which is optimal.

I feel that on top of this Xanadu can be build.