Eric Lippert has another post up in his immutability series, this one about using immutable binary trees to represent immutable maps. (“Map” = “hash” or “dictionary”, for you perl and python folks. I understand that the technical term is “associative array.”)
I skimmed the post, said to myself “that makes sense,” then went back and stared at the code samples for a bit and said “wait a minute….” Because the map interface has methods like
Remove(), and so does the tree interface. What’s immutable about that?
I was halfway through writing a comment asking Mr. Lippert what the hell was going on, when I figured it out. Yes, you can call
Remove(), but those methods don’t actually modify the map (or the tree) you call them on. Instead — this is what I saw, when I looked closely — they return a new map (or tree), identical to the original apart from whatever was added or removed. Instead of mutators that change the internal state of an object, you have something much closer to a mathematical function, describing a relationship but never altering any values.
Anyway, it turns out that if I’d actually read all of Mr. Lippert’s other posts, he explains all this, specifically in post #2 of the series, “A Simple Immutable Stack.” He goes on to demonstrate how, contra most people’s first instincts including mine, immutable data structures of this kind can actually use less memory than the traditional mutable kind, because, being as all the pieces they’re built up out of are also immutable, they can safely share as much of their internal state as they have in common.
It strikes me that something like this is probably the answer to Dan‘s question about representing mutable state in functional languages. Functional expressions may not be able to modify anything, but they can always produce new results.
(The “Item 13” in the title is from Effective Java: Item 13: Favor Immutability. Since it’s the Bible, we might as well cite chapter and verse — as long as the numbers haven’t changed in the second edition.)
Comments closed due to spam.