Ralf Hinze has a paper Constructing Red-Black Trees which is cached on Citeseer http://www.comlab.ox.ac.uk/people/publications/date/Ralf.Hinze.html http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.2171 I thought someone turned the implementation in the paper into a library on Hackage, but I can't find it either.