我的類型簽名在這裏有什麼問題？

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可讓您的代碼類型檢查我。