I dug this haskell code of the internet wayback machine. Don't worry, Dons - it may be old; but it's still Golden. . . it seems to be from the Okasaki book with a working delete and key-value variant: http://web.archive.org/web/20100629235553/http://www.cse.unsw.edu.au/~dons/d... I'm still at the lower end of Haskell expertise; but I can read this, and am porting the concept into my Heresy library for CL. The algorithm seems to be proven via some haskell static means (that I don't fully understand); but it also holds up to my heavy unit tests. What I value from functional containers, though, is that the modded structure shares the bulk of its identity/nodes with the prior variant. However, I added sharing as a metric to my unit test, so it can also discover when a new (by identity) node exists in the modified/new reference that is logically analogous to a node the old/prior one. . . . . which would waste space if people are holding various references to evolving containers. When purely translating this code, even in zero-change cases, one function will build a red node from a black, only to have the caller use *that* to build a brand new black - as across the 2 levels it has no way of seeing that the optimal node is merely the original node. Through some fundamental changes, and a bit of "whack a mole" (especially in the delete case) I *think* I caught and removed them all. . . . Anyway, my point: It seems that these containers can be analyzed with respect to their pure algorithm/logical correctness; but also structural storage. Is there much talk on that side of the issue? Is there any cardinal reference for this or similar data structures with the storage issue resolved? I'd be interested in looking at another implementation, especially one where the size issue isn't just tested; but proven. . . .