[Haskell-cafe] Cardinal Haskell RBTree? And structural sharing.

Matt Lamari matt.lamari at gmail.com
Sun May 20 22:34:03 CEST 2012

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:


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. . . .

More information about the Haskell-Cafe mailing list