The reason he cites union-find is that it is one of the only significant data structures where sustained research hasn't either produced an immutable version with the same performance as the mutable one or demonstrated that one can't exist.

It's a great puzzle, but it's not a huge drawback because subbing in IntMap or something really _does_ give adequate performance for typical union-find cases (unification or the like). Which is to say, the performance gap left to be closed is almost certainly _not_ where the important improvements to unification algorithms are made (which have to do with being able to impose a lot more particular structure on the types of things being unified, etc).