...

The breakage to code will be fairly minimal: Data.FiniteMap can be left in place but deprecated, many of the operations from Data.Set can also be provided by the new Data.Set (but deprecated, of course). The other modules don't conflict.

By the way, is there already a mechanism for marking deprecated code? Will deprecated code be removed some time or will it pollute the libraries until the end of time?

GHC has a DEPRECATED pragma: http://www.haskell.org/ghc/docs/latest/html/users_guide/pragmas.html#DEP RECATED-PRAGMA There really ought to be a way in Haddock to indicate deprecated interfaces too. As a rule of thumb, something that is DEPRECATED will last for at least two major releases of GHC (DEPRECATED in one major release, still available in the next, then removed). We sometimes keep things longer than this, though. There have been instances where things have been removed early too - this should only happen in libraries that are marked "experimental" though. Cheers, Simon