4

我正在使用 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签名相同吗？nodesedgesa

4

1 回答 1

6

我在这里做错了什么？我猜测类型变量 a 不受 mkGraph 的类型签名的约束，但 mkGraph 的定义不应该强制节点和边的签名中的 a 相同吗？

你猜对了；另一个a是新类型变量。这意味着，它不仅与ainmkGraph的签名不同，而且是一个全新的通用量化类型变量，这是不正确的。因此，您的内部签名中调用的类型a既不是多态的，也不是单一的已知类型。不，根据 Haskell 标准，它“不应该”。nodes在 Haskell 98 中，实际上不可能edges在代码中编写类型签名。是的，这有点傻。

但是，GHC 提供了一个ScopedTypeVariables扩展来允许这样做，除此之外。GHC 用户指南的相关部分也讨论了前面提到的“不可能的类型签名”问题。

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

于 2010-11-08T16:23:56.263 回答