The Wikipedia entry seems to allow for data structures that maintain the history internally, i.e. unlike the typica copy-semantics of functional languages.
Anyway, "immutability" is overloaded, esp. so in OOP. Can the structure change in memory, or are you only interested in the same "view" (wrt its methods)?