I think the Haskell example should've used this type signature instead. Compared to the OP's example, this has a much stronger implication. There's very few implementations of this type that would make sense, whereas with the other one - it could be 'count' of the number of times 'string' shows up in the map; Or it could be number of letters in the provided string (ignoring the map entirely); Or it could be (key - 1); or any number of other things.
Here, you can't just magic into existence or modify an unknown 'a' value.
I think it's still pretty unclear what this function might do, since the inverse of a map isn't well-defined. I think this is a type signature that makes sense and has a fairly obvious most-likely meaning:
boo :: Map a b -> b -> Set a
I'm not sure how you would conjure up just an 'a' in general.