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

G>Гм... если что — прошу смеяться громко, чтобы проняло.

Уговорил.

G>На это безобразие компилер (The Glorious Glasgow Haskell Compilation System, version 6.4.2) я так подозреваю законно ругается

Правильно подозреваешь.

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

Не очень понял твою мысль, но на правду похоже.

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

Вариант раз: определить класс для "обёртки" GovnoMap — в предполжении, что любой инстанс Map может хранить значения и ключи произвольного типа:

module Maps where

data MapNode key value = Null | 
                         Leaf key value | 
                         Node (MapNode key value) key value (MapNode key value)
                         deriving Show

class Map m where 
    insert :: m k v -> k -> v -> m k v
    erase :: m k v -> k -> m k v
      
data GovnoMap key value = GovnoMap { root :: MapNode key value } deriving Show

instance Map GovnoMap where
    insert m@(GovnoMap Null) k v = m{root=Leaf k v}

Вариант два: ввести в определение класса типы ключей и значений, в предположении, что инстанс всегда будет некоей "обёрткой", то есть будет иметь вид "Что-то-там key value".

{-# OPTIONS_GHC -fglasgow-exts #-}
-- нужно, поскольку классы с несколькими параметрами - расширение GHC.

module Maps where

data MapNode key value = Null | 
                         Leaf key value | 
                         Node (MapNode key value) key value (MapNode key value)
                         deriving Show

class Map m k v where 
    insert :: m k v -> k -> v -> m k v
    erase :: m k v -> k -> m k v
      
data GovnoMap key value = GovnoMap { root :: MapNode key value } deriving Show

instance Map GovnoMap key value where
    insert m@(GovnoMap Null) k v = m{root=Leaf k v}

Вариант три: использовать фундепсы (тоже расширение GHC). Это — самый прямой вариант.

{-# OPTIONS_GHC -fglasgow-exts #-}
module Maps where

data MapNode key value = Null | 
                         Leaf key value | 
                         Node (MapNode key value) key value (MapNode key value)
                         deriving Show

class Map m k v | m -> k, m -> v  where 
    insert :: m -> k -> v -> m
    erase :: m -> k -> m
      
data GovnoMap key value = GovnoMap { root :: MapNode key value } deriving Show

instance Map (GovnoMap key value) key value where
    insert m@(GovnoMap Null) k v = m{root=Leaf k v}

Вообще, ты столкнулся с типичной проблемой коллекций в хаскеле. Без расширений она по нормальному не решается.