Immutability and shared references - how to reconcile?

Question

Consider this simplified application domain:

• Criminal Investigative database
• Person is anyone involved in an investigation
• Report is a bit of info that is part of an investigation
• A Report references a primary Person (the subject of an investigation)
• A Report has accomplices who are secondarily related (and could certainly be primary in other investigations or reports
• These classes have ids that are used to store them in a database, since their info can change over time (e.g. we might find new aliases for a person, or add persons of interest to a report)

Domain http://yuml.me/13fc6da0

If these are stored in some sort of database and I wish to use immutable objects, there seems to be an issue regarding state and referencing.

Supposing that I change some meta-data about a Person. Since my Person objects immutable, I might have some code like:

class Person(
    val id:UUID,
    val aliases:List[String],
    val reports:List[Report]) {

  def addAlias(name:String) = new Person(id,name :: aliases,reports)
}

So that my Person with a new alias becomes a new object, also immutable. If a Report refers to that person, but the alias was changed elsewhere in the system, my Report now refers to the "old" person, i.e. the person without the new alias.

Similarly, I might have:

class Report(val id:UUID, val content:String) {
  /** Adding more info to our report */
  def updateContent(newContent:String) = new Report(id,newContent)
}

Since these objects don't know who refers to them, it's not clear to me how to let all the "referrers" know that there is a new object available representing the most recent state.

This could be done by having all objects "refresh" from a central data store and all operations that create new, updated, objects store to the central data store, but this feels like a cheesy reimplementation of the underlying language's referencing. i.e. it would be more clear to just make these "secondary storable objects" mutable. So, if I add an alias to a Person, all referrers see the new value without doing anything.

How is this dealt with when we want to avoid mutability, or is this a case where immutability is not helpful?

Answer 1

If X refers to Y, both are immutable, and Y changes (i.e. you replace it with an updated copy), then you have no choice but to replace X also (because it has changed, since the new X points to the new Y, not the old one).

This rapidly becomes a headache to maintain in highly interconnected data structures. You have three general approaches.

• Forget immutability in general. Make the links mutable. Fix them as needed. Be sure you really do fix them, or you might get a memory leak (X refers to old Y, which refers to old X, which refers to older Y, etc.).
• Don't store direct links, but rather ID codes that you can look up (e.g. a key into a hash map). You then need to handle the lookup failure case, but otherwise things are pretty robust. This is a little slower than the direct link, of course.
• Change the entire world. If something is changed, everything that links to it must also be changed (and performing this operation simultaneously across a complex data set is tricky, but theoretically possible, or at least the mutable aspects of it can be hidden e.g. with lots of lazy vals).

Which is preferable depends on your rate of lookups and updates, I expect.