Was ist los mit hier meine Art Unterschriften?

Question

Ich spiele um mit corecursive Datenstrukturen und ziemlich früh in meinem Code, ich habe eine Art Fehlermeldung erhalten:

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

Wenn ich versuche, dies in ghci zu laden, erhalte ich

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

Wenn ich den Typ löschen Signaturen nodes :: Map a (Node a) und edges :: [Edge a], der Fehler geht weg.

Was mache ich hier falsch? Ich vermute, dass die Variable vom Typ a nicht durch mkGraph der Art Unterschrift gebunden zu sein, sollte aber nicht die Definition von mkGraph die a in der Signatur von nodes zwingen und edges die gleiche a sein?

Answer 1

  

Was mache ich hier falsch? Ich vermute, dass der Typ Variable a wird nicht durch mkGraph der Art Unterschrift gebunden zu sein, sollte aber nicht die Definition von mkGraph die einen in der Signatur von Knoten zwingen und Kanten das gleiches eines sein?

erraten Sie richtig; der andere a ist eine frische Art variabel. Dies bedeutet, dass nicht nur ist es nicht das gleiche a wie in mkGraph Unterschrift, es ist ein brandneues allquantifizierte Typ Variable, die nicht korrekt ist. Die Typen genannt a in Ihrem inneren Signaturen sind somit weder polymorphe noch einzelne bekannte Typen. Und nein, es „sollte nicht“, gemäß dem Haskell-Standard. In Haskell 98 ist es in der Tat unmöglich, eine Art Signatur für nodes und edges in Ihrem Code zu schreiben. Ja, das ist irgendwie albern.

Allerdings sieht GHC ein ScopedTypeVariables Erweiterung , die dies unter anderem ermöglicht. Der entsprechende Abschnitt der GHC Anleitung beschreibt auch die zuvor erwähnt „unmögliche Art Unterschrift“ -Problem.

Beachten Sie, dass Sie auch benötigen, um eine explizite forall in der Art Signatur für mkGraph hinzuzufügen, das heißt forall a. (Ord a) => [(a,a)] -> Graph a den Typ Variable in Umfang zu bringen. Aktivieren der Erweiterung und das Hinzufügen der forall können Sie Ihren Code Typprüfung für mich.