Immutability is a hard topic to breach. As a programmer used to modeling the world, you might object to immutable data structures. How do you model a changing world? Why would you choose to use immutable data structures when everything in the world is changeable?
Let's do a little thought experiment. Let's look at a nice mutable system: paper and pencil. You can write, erase, and write again. It's very convenient. It lets you correct mistakes. And when you don't need something anymore, you can easily erase it.
Now answer this: would you trust a bank that used pencils to record transactions? It would be easy: whenever you would withdraw money, they would erase the old balance and write the new balance. And if you transferred money from one account to another, they'd erase two balances and write the new ones in. It may sound great, but there's a reason banks don't use pencils: they want to be sure nothing has changed. That sounds like immutability.
This is a bank ledger. Each transaction gets its own line. Always done in pen. It's an example of an append-only data structure. You can answer questions about the past like "How much money was in the account at the close of last Tuesday?" by going up lines until you find the last entry for Tuesday. And you can do that because you never modify existing entries. You only add new entries on blank lines.
This is another example of an append-only data structure in the real world: medical records. Each patient gets a file that everything is added to. You never modify old records. That way, everything is recorded, even the wrong diagnoses (mistakes) of the doctor.
It turns out that traditional information systems that need a high degree reliability create immutable records out of mutable paper. Even though you could in theory scratch out some data and write it again, or white it out, or find some other way to mutate the document, a mark of professionalism in the job is to discipline yourself to adhere to strict append-only behaviors.
Wouldn't it be nice if the machine took care of the discipline for us? Even though RAM and disk are mutable like paper and pen, we can impose a discipline inside of our program. We could rely on the programmer to never accidentally overwrite existing data. But that's just shifting the burden. Instead, we can build in immutability into our data structures and make a paper that cannot be overwritten.
That's how immutable data structures work. All new pieces of information are written to new locations in memory. Only when it is proven that a location is never going to be used again is it reused.
Reliable paper-based systems use immutable data. There was a time when computer memory was expensive and we had to reuse storage, so we couldn't make immutable systems. But RAM is cheap now! We should be using immutable data, just as banks have done for hundreds of years. Ready to join the 13th century?1
If you're interested in a language with a very cool set of powerful immutable data structures, probably the most cutting edge immutable data structures in any language, you're in luck! Check out LispCast Introduction to Clojure at PurelyFunctional.tv. It's a video course with animations, exercises, and screencasts that teaches you Clojure.
The Double-entry method of accounting can trace its history back to 13th century Florence. ↩