我的类型签名在这里有什么问题？

Question

我玩弄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？

Answer 1

What am I doing wrong here? I'm guessing that the type variable a isn't being bound by mkGraph's type signature, but shouldn't the definition of mkGraph compel the a in the signature of nodes and edges to be the same a?

你猜对了;另一个a是一个新鲜的类型变量。这意味着，它不仅与mkGraph的签名a不一样，而且是全新量化的类型变量，这是不正确的。因此内部签名中称为a的类型既不是多态也不是单个已知类型。不，根据Haskell标准，它“不应该”。在Haskell 98中，实际上不可能在代码中编写nodes和edges的类型签名。是的，那很愚蠢。

但是，GHC提供了一个ScopedTypeVariables extension，允许这个，等等。 GHC用户指南的相关部分还讨论了上述“不可能的类型签名”问题。

请注意，您还需要在mkGraph的类型签名中添加明确的forall，即forall a. (Ord a) => [(a,a)] -> Graph a以将类型变量纳入范围。启用扩展并添加forall可让您的代码类型检查我。