Implementing immutable collections

I have a general question regarding immutable collections. I will be using Java as a reference lab as I know it.

First, is there a general approach to ensuring immutability? By that I mean, do I have to copy the entire collection, make changes and then return a new object? Is there a more complex general approach?

Taking this a little further, how about "obvious" (to me) mutable collections like trees? They are usually implemented as nodes with N child nodes. How could you guarantee immutability in this case? Clone and copy all recursive links?

Following the above, I was wondering if there would be a better approach for these collections:

  • List is an array that we will copy before making changes.
  • Queues - two arrays front and back, cloned before returning? How about a bode based implementation?
  • Trees
  • Hashmap - copy bucket array as well as all conflict lists?
  • Set

Thanks a lot for your answers.

+3


source to share


4 answers


Luckily, a lot of this is already done for you, have a look at google guava which has ImmutableCollection , ImmutableList , ImmutableSet , ImmutableMap , etc.

Non-recoverability is provided by preventing subclasses of these classes (by terminating them permanently or by closing their constructors).



When you make an immutable collection from a mutable, the data in the mutable collection is copied, then all mutation operations are prohibited - they will throw an exception (for example UnsupportedOperationException

).

For performance reasons, guava libraries will do their best not to copy data if they don't need to. For example, if you already have ImmutableMap

and create a new one with ImmutableMap.copyOf(theOtherImmutableMap)

, then no data will be copied, since we already know that the other card is unchanged and it has two references to the same data.

+5


source


From a Java perspective, the collection class is your friend. Instead of doing these operations manually, I would suggest working through the provided API. In particular, take a look at immutable and non-modifiable methods.

For example, in terms of immutability, there is:

<T> List<T>
emptyList() 
          Returns the empty list (immutable).
static
<K,V> Map<K,V>
emptyMap() 
          Returns the empty map (immutable).
static
<T> Set<T>
emptySet() 
          Returns the empty set (immutable).

      



For unmodifiables you:

static
<T> Collection<T>
unmodifiableCollection(Collection<? extends T> c) 
          Returns an unmodifiable view of the specified collection.
static
<T> List<T>
unmodifiableList(List<? extends T> list) 
          Returns an unmodifiable view of the specified list.
static
<K,V> Map<K,V>
unmodifiableMap(Map<? extends K,? extends V> m) 
          Returns an unmodifiable view of the specified map.
static
<T> Set<T>
unmodifiableSet(Set<? extends T> s) 
          Returns an unmodifiable view of the specified set.
static
<K,V> SortedMap<K,V>
unmodifiableSortedMap(SortedMap<K,? extends V> m) 
          Returns an unmodifiable view of the specified sorted map.
static
<T> SortedSet<T>
unmodifiableSortedSet(SortedSet<T> s) 

      

There are other and some strategies you can implement under it, but I would start there.

+2


source


I assume that you intend to understand how immutable collections work within functional languages ​​(like haskell, etc.). The idea is that all collections are immutable and final, which avoids all the multi-threading bugs regarding mutability, synchronization, etc., but still allows you to add and remove and modify as if they were mutable

The best examples I've seen for this were in the Clojure source code . It is a lisp -like language and therefore deals with immutable collections as a core feature. I highly recommend looking at how collections are implemented in clojure as they will answer many of your questions. Probably some things will be too complicated (I still don't understand trying ). See here and good luck

0


source


Clojure contains such immutable (or persistent) collections .

It provides all the collections you use and supports mutation-through-construct: by simply adding or removing new elements, you get a new collection that generally reuses large parts of the old collection thanks to clever use of Trie-type.

By themselves, they are poorly suited for use in straight Java - they are intended for use in Clojure.

Pure4j is an attempt to bring these (and immutable / value based style) to the Java language. Perhaps this is what you need.

Disclaimer: I am the developer of Pure4J

0


source







All Articles