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

Question

我正在研究核心递归数据结构，并且在我的代码中很早就出现了类型错误:

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是一个新的类型变量。这意味着，不仅不一样 a如 mkGraph的签名，它是一个全新的通用量化类型变量，这是不正确的。被称为 a 的类型因此，在您的内部签名中既不是多态的也不是单一的已知类型。不，根据 Haskell 标准，它“不应该”。在 Haskell 98 中，实际上是不可能为 nodes 写类型签名的。和 edges在你的代码中。是的，这有点傻。

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

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