Your confusion might be due to the fact that the Map type was previously part of the package purescript-maps, but now lives in purescript-ordered-containers. Incidentally, if you’re using Bower, you can check which version of a given package you’re using by having a peek at bower_components/<package>/.bower.json.
Perhaps mapWithKey was removed after being made redundant by the FunctorWithIndex class?