The actual function would be written more like

    invMap :: forall k v. (Eq v, Eq k) =>
              Map k v -> v -> Set k

The parametricity means that while this function may get specialized to have v ~ String and k ~ Int, we can be sure that invMap isn't using that information. Instead, with the typeclass restriction, we know that the only thing the function can be doing internally to the ks and vs is comparing them for equality.

Intuitively, invMap can either be computing the Set of ks which hold a particular v or, maybe, the set of ks which don't hold that value and not much else.