Что не так с моей подписью типа здесь? - PullRequest
Новая
       19

Что не так с моей подписью типа здесь?

4 голосов
/ 08 ноября 2010

Я играю с corecursive структурами данных, и довольно рано в моем коде я получаю ошибку типа: 

module Graph where
import Data.Map 

data Node a = Node { getLabel :: a, getInEdges :: [Edge a], getOutEdges :: [Edge a] }
data Edge a = Edge { getStart :: Node a, getEnd :: Node a }
data Graph a = Graph { getNodes :: [Node a], getEdges :: [Edge a] }

mkGraph :: (Ord a) => [(a,a)] -> Graph a
mkGraph pairs = Graph (elems nodes) edges
  where nodes :: Map a (Node a)
        edges :: [Edge a]
        (nodes, edges) = foldr addEdge (empty,[]) pairs
        addEdge :: (a,a) -> (Map a (Node a), [Edge a]) -> (Map a (Node a), [Edge a])
        addEdge (startLabel, endLabel) = undefined

Когда я пытаюсь загрузить это в ghci, я получаю 

graph.hs:13:25:
    Couldn't match expected type `forall a. Map a (Node a)'
           against inferred type `Map a (Node a)'
      Expected type: (forall a1. Map a1 (Node a1), forall a1. [Edge a1])
      Inferred type: (Map a (Node a), [Edge a])
    In the expression: foldr addEdge (empty, []) pairs
    In a pattern binding:
        (nodes, edges) = foldr addEdge (empty, []) pairs

Если я удаляю сигнатуры типов nodes :: Map a (Node a) и edges :: [Edge a], ошибка исчезает.

Что я здесь не так делаю?Я предполагаю, что переменная типа a не связана с сигнатурой типа mkGraph, но определение mkGraph не должно заставлять a в сигнатуре nodes и edgesбыть таким же a?

1 Ответ

6 голосов
/ 08 ноября 2010

Что я здесь не так делаю? Я предполагаю, что переменная типа a не связана с сигнатурой типа mkGraph, но не должно ли определение mkGraph заставить a в сигнатуре узлов и ребер быть одинаковыми a?

Вы правильно угадываете; другая a - переменная нового типа. Это означает, что это не только a, что и в сигнатуре mkGraph, но и совершенно новая переменная типа с универсальным определением , что неверно. Таким образом, типы, называемые a в ваших внутренних сигнатурах, не являются ни полиморфными, ни единственными известными типами. И нет, это "не должно", согласно стандарту Haskell. В Haskell 98 фактически невозможно написать сигнатуру типа для nodes и edges в вашем коде. Да, это глупо.

Однако GHC предоставляет ScopedTypeVariables расширение , которое позволяет это, помимо прочего. В соответствующем разделе руководства пользователя GHC также обсуждается вышеупомянутая проблема «подписи невозможного типа».

Обратите внимание, что вам также необходимо добавить явный forall в сигнатуру типа для mkGraph, то есть forall a. (Ord a) => [(a,a)] -> Graph a, чтобы перевести переменную типа в область видимости. Включение расширения и добавление forall позволяет мне проверить тип вашего кода.

...