Здравствуйте, Garrrrr, Вы писали:

G>Я так догадался, что он хочет на этапе компиляции (без даже примеров использования ф-ий) быть уверенным, что тип key из instance равен типу k из instance::insert, но это противоречит правилам вывода типов для обычных функций.

Да.

G>Требуется подсказка — как это исправить и почему в данном случае компилятор накладывает такие жесткие ограничения

Ограничения не жесткие — это же язык со статической типизацией.
Исправить можно, явно привязав k и v к Map:

class Map m where 
      insert :: m k v -> k -> v -> m k v
      erase :: m k v -> k -> m k v

instance Map GovnoMap
         where
...