Cosa c'è di sbagliato con il mio tipo firme qui?

Question

Sto giocando intorno con strutture di dati corecursive, e abbastanza presto nel mio codice, ottengo un errore di tipo:

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

Quando provo a caricare questo in ghci, ottengo

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

Se cancello il tipo firme nodes :: Map a (Node a) e edges :: [Edge a], l'errore va via.

Che cosa sto facendo male qui? Sto indovinando che il a tipo di variabile non viene vincolata dalla firma di tipo di mkGraph, ma non dovrebbe la definizione di mkGraph costringere il a nella firma di nodes e edges essere la stessa a?

Answer 1

  

Che cosa sto facendo male qui? Sto indovinando che la variabile di tipo A non è vincolata dalla firma di tipo di mkGraph, ma non avrei la definizione di mkGraph costringere l'una nella firma di nodi e bordi per essere lo stesso di un?

È indovinare correttamente; l'altro a è una variabile di tipo fresco. Ciò significa che, non solo non è lo stesso a come nella firma di mkGraph, si tratta di un nuovo marchio universalmente quantificata tipo di variabile, che non è corretto. I tipi di chiamate a nelle vostre firme interne sono quindi tipi noti né polimorfici né singoli. E no, "non dovrebbe", secondo lo standard Haskell. In Haskell 98, è infatti impossibile scrivere una firma tipo per nodes e edges nel codice. Sì, questo è il tipo di sciocco.

Tuttavia, GHC fornisce un rel ScopedTypeVariables estensione che permette questo, tra le altre cose. La sezione del manuale d'uso GHC discute anche il suddetto problema "firma tipo impossibile".

Si noti che avrete anche bisogno di aggiungere un forall esplicita nella firma tipo per mkGraph, vale a dire, forall a. (Ord a) => [(a,a)] -> Graph a per portare la variabile di tipo nel campo di applicazione. Abilitazione l'estensione e l'aggiunta del forall lascia il tipo di controllo di codice per me.