Блог

У меня возникла простая проблема, когда дело доходит до написания классов типов, которые наследуются друг от друга. Я пытаюсь создать иерархию классов типов для достижения некоторого уровня абстракции представления. Допустим, мне нужен класс типов collections:

 {-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}

class Collection c a where
  isMember :: a -> c -> Bool
  

И я определил тип дерева:

 data Tree a = Empty | Node a (Tree a) (Tree a)
  deriving (Show, Eq)
  

Я хотел бы сделать свое дерево коллекцией, поэтому:

 inOrder :: Tree a -> [a]
inOrder Empty = []
inOrder (Node a l r) = (inOrder l)    [a]    (inOrder r)

instance (Eq a) => Collection (Tree a) a where
  isMember a c = a `elem` (inOrder c)
  

Это работает не совсем правильно:

 *Main> (isMember '2' Empty)
<interactive>:1:1:
    No instance for (Collection (Tree a) Char)
      arising from a use of `isMember' at <interactive>:1:1-18
    Possible fix:
      add an instance declaration for (Collection (Tree a) Char)
    In the expression: (isMember '2' Empty)
    In the definition of `it': it = (isMember '2' Empty)
  

Предположительно, значение класса типов было бы потеряно, если бы мне пришлось создавать реализацию для каждого конкретного типа. Итак, я неправильно пишу объявление экземпляра. Но я не совсем понимаю, как поступить.

Проблема здесь в том, что по умолчанию каждый параметр класса type не зависит от других. Простого применения isMember к Char и дереву неизвестного типа элемента недостаточно, чтобы позволить ему сделать вывод, что он должен использовать (казалось бы, очевидный) экземпляр.

Это явно не то, как вы хотите, чтобы это работало, и немного глупо при загрузке, но именно так это работает. Чтобы справиться с проблемой, вам нужно предоставить ему какой-то способ установления соединения, для чего существуют другие расширения: FunctionalDependencies является более распространенным, хотя TypeFamilies и более новым и гораздо более удобным в использовании, но все еще имеет некоторые шероховатости.

В случае функциональных зависимостей вы должны указать, что некоторое подмножество параметров класса типов полностью определяет другие, например Collection c a | c -> a . Это имеет свои подводные камни, но работает достаточно хорошо во многих случаях.

С семействами типов вы, вероятно, сократили бы это до класса типа с одним параметром, с соответствующим типом элемента, например:

 class Collection c where
    type Elem c
    isMember :: Elem c -> c -> Bool
  

Необходимо добавить функциональную зависимость, чтобы указать, что тип контейнера определяет тип элемента:

 {-# LANGUAGE FunctionalDependencies #-}

class Collection c a | c -> a where
    ...
  

Есть и другие способы сделать это, например, используя семейства типов, но я думаю, что это самое простое решение в данном случае.

Проблема в том, что Empty тип является Tree a , а ghc не располагает достаточной информацией, чтобы знать, что вы хотите, чтобы в этом случае a было Char . Если вы вручную укажете тип, это сработает:

 isMember '2' (Empty::Tree Char)
  

Причина, по которой ghc не может просто сделать вывод, что a должно быть Char , заключается в том, что теоретически у вас может быть один экземпляр Collection (Tree Char) Char и другой Collection (Tree Int) Char . В этом случае не было бы способа определить, какой из них следует использовать, если вы не укажете это явно.