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.