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

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

我在这里做错了什么？我猜想类型变量A不受Mkgraph类型签名的限制，但是Mkgraph的定义是否不应该强迫a在节点和边缘的签名中a的定义是相同的A吗？

你猜正确了；另一个 a 是一个新的类型变量。这意味着，不仅不一样 a 如 mkGraph的签名，这是一个全新的 普遍量化 类型变量，这是不正确的。调用的类型 a 因此，在您的内部签名中既不是多态的也不是单一类型。不，根据Haskell标准，它“不应该”。在Haskell 98中，实际上不可能为 nodes 和 edges 在您的代码中。是的，这很愚蠢。

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

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