¿Qué hay de malo en mis declaraciones de tipo aquí?

Question

Estoy jugando con las estructuras de datos corecursive, y bastante pronto en mi código, aparece un error de tipo:

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

Cuando intento cargar esto en ghci, consigo

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 elimino el tipo firmas nodes :: Map a (Node a) y edges :: [Edge a], el error desaparece.

¿Qué estoy haciendo mal aquí? Supongo que el tipo de variable a no se está obligado por la firma tipo de mkGraph, pero no debe la definición de mkGraph obligar al a en la firma de nodes y edges a ser el mismo a?

Answer 1

  

¿Qué estoy haciendo mal aquí? Supongo que la variable de tipo A no se está obligado por la firma tipo de mkGraph, pero no debería mkGraph la definición de obligar a la una en la firma de nodos y bordes a ser el mismo una?

adivinar correctamente; el otro a es una variable de tipo fresco. Esto significa que, no sólo no es la misma a como en la firma de mkGraph, es una nueva marca universalmente cuantificada variable de tipo, lo cual es incorrecto. Los tipos llamados a en sus firmas internas son, pues, los tipos conocidos ni polimórficas ni individuales. Y no, "no debería", según el estándar de Haskell. En Haskell 98, de hecho, es imposible escribir una firma tipo para nodes y edges en el código. Sí, eso es un poco tonto.

Sin embargo, GHC proporciona un rel ScopedTypeVariables extensión que permite, entre otras cosas. La sección correspondiente de la guía del usuario GHC también discute el mencionado problema "tipo de firma imposible".

Tenga en cuenta que también tendrá que añadir un forall explícita en la declaración de tipo de mkGraph, es decir, forall a. (Ord a) => [(a,a)] -> Graph a para llevar la variable de tipo en el alcance. Permitiendo la extensión y la adición de la forall le permite a su tipo de comprobación de código para mí.