News for hackers. Stuff that matters.
Re:Red-Black Trees in a Functional Setting (Okasaki, 1993) by leif on Tuesday March 16, 2010 @01:50AM (#1195139)
This is probably the best explanation of Red-Black trees, even outside of a functional setting.

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.

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.
Re:Red-Black Trees in a Functional Setting (Okasaki, 1993) by eru on Tuesday March 16, 2010 @07:06AM (#1195426)
Yes, that's the power of purity. On the syntax side, or-patterns express those remaining four cases very succinctly.