Quel est le problème avec mes signatures de type ici?

Question

Je joue autour des structures de données corecursive, et assez tôt dans mon code, je reçois une erreur de type:

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

Lorsque je tente de charger cela dans ghci, je reçois

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

Si je supprime les signatures de type nodes :: Map a (Node a) et edges :: [Edge a], l'erreur disparaît.

Qu'est-ce que je fais mal ici? Je devine que la a variable de type n'est pas lié par la signature de type de mkGraph, mais ne devrait pas la définition de mkGraph obliger le a dans la signature de nodes et edges être le même a?

Answer 1

  

Qu'est-ce que je fais mal ici? Je devine que la variable de type est un pas lié par la signature de type de mkGraph, mais ne devrait pas la définition de mkGraph contraindre un dans la signature des noeuds et des arêtes être le même un?

Vous devinez correctement; l'autre a est une variable de type frais. Cela signifie que, non seulement il est pas le même a que dans la signature de mkGraph, il est une nouvelle marque universellement quantifiée variable de type, ce qui est incorrect. Les types appelés a dans vos signatures internes ne sont donc ni polymorphes ni simples types connus. Et non, il « ne devrait pas », selon la norme Haskell. Dans Haskell 98, il est en effet impossible d'écrire une signature de type pour nodes et edges dans votre code. Oui, c'est un peu ridicule.

Cependant, GHC fournit un l'extension ScopedTypeVariables qui permet, entre autres. La section pertinente du guide utilisateur GHC aborde également le problème mentionné ci-dessus "de la signature de type impossible".

Notez que vous aurez également besoin d'ajouter un forall explicite dans la signature de type pour mkGraph, à savoir forall a. (Ord a) => [(a,a)] -> Graph a pour amener la variable de type dans le périmètre. L'activation de l'extension et l'ajout de la forall permet de vérifier votre type de code pour moi.