Re:Red-Black Trees in a Functional Setting (Okasaki, 1993)
by kapuzineralex on Tuesday March 16, 2010 @03:35AM
(#1195239)
I find it particularly interesting that he breaks down the number of neccessary cases to only 4 compared to the standard explanation found everywhere else.
There is an implementation that is pretty faithful to Okasaki's paper here: http://www.cs.kent.ac.uk/people/staff/smk/redblack/Untyped.h... . I used as a reference once because it also implements delete.
In the same directory, Kahrs develops other versions with stronger constraints coming from the type system, but I never got far enough in to Haskell back then to understand them.