What happened to my type signatures here?

Question

I play with core recursive data structures, and pretty early in my code, I get an error like:

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 

When I try to upload this to ghci , I get

 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 

If I remove signatures like nodes :: Map a (Node a) and edges :: [Edge a] , the error disappears.

What am I doing wrong here? I assume that a variable of type a not bound by the tick signature of mkGraph , but the definition of mkGraph should not force a in the nodes and edges signature to be the same a ?

Answer 1

What am I doing wrong here? I assume that a variable of type a is not associated with a signature of type mkGraph, but there should not be a definition of mkGraph so that a in the signature of nodes and edges are the same a?

You understood correctly; another a is a variable of a new type. This means that not only is it not the same a as in the mkGraph signature, it is a completely new universal quantitative variable of the type that is incorrect. Thus, types called a in your internal signatures are neither polymorphic nor uniform. And no, this “shouldn't”, according to the Haskell standard. In Haskell 98, it's actually not possible to write a type signature for nodes and edges in your code. Yes, this is stupid.

However, the GHC ScopedTypeVariables provide a ScopedTypeVariables extension that allows this, among other things. The relevant section of the GHC User Guide also discusses the aforementioned “signature impossibility to sign” problem.

Note that you will need to add an explicit forall to the type signature for mkGraph , i.e. forall a. (Ord a) => [(a,a)] -> Graph a forall a. (Ord a) => [(a,a)] -> Graph a to add a type variable to the scope. Enabling the extension and adding forall allows me to check the type of code for me.