Ross Esmond

Code, Prose, and Mathematics.

portrait of myself, Ross Esmond
Written — Last Updated


An Invariant is a requirement placed on the program state that must remain satisfied after all state changes. The program should only violate the invariant while transitioning state, and then only if the data is protected from access during the transition. Invariants simplify state processing, as they constrain the variability of state. Conversely, invariants complicate state updates, as any change to state must take the invariant into account. It is best, then, to abstract state updates behind an interface that makes breaking the invariant impossible. When an invariant is built into the structure of the value, it is called a Morphological Invariant.

Morphological Invariant

A morphological invariant is one that cannot be broken due to the structure of the state, as the structure cannot accommodate a change that would break the invariant. An array satisfies the morphological invariant that its elements maintain a simple order, whereas a map satisfies the morphological invariant that each element has a unique key. Consider, however, if the program required that a collection of elements must have both a simple order and a unique key for every element. The programmer would then have to choose between an array, a map, or neither. If they choose an array, they would then need to constrain changes to the array such that the non-morphological invariant of unique keys is always satisfied. This could be achieved by wrapping the array in an object that manages all changes and ensures they do not break the invariant. The invariants would then become morphological, as they are maintained by the value itself—the new custom collection.

Maintaining Invariants

When a change to a value would break an invariant there are several ways to handle the update. The most obvious is that the update could fail, which could happen silently or with a thrown error. The most common way to handle the update with collections, however, is to just remove the conflicting prior value. When you set the fifth value in an array, the prior fifth value is replaced. Similarly, when you set the “foo” value in a map, the prior “foo” value is replaced. If you wished to create an ordered map in the same way, you could write an add function that takes an element, a key, and an optional position. If the key or position is already taken, the elements that those identifiers point to would be removed, such that the new element could be added without breaking the invariant.