Haskell不能匹配類型，聲明剛性變量

Question

我是Haskell的新手，我正在爲創建圖形及其中的節點創建一個類型類來玩。既然我想要有向圖和無向圖，我有

data Node = Node { label :: Char 
       , index :: Int 
       } deriving (Ord, Eq) 
type Graph edgeType = ([Node], [edgeType]) 
data Edge = DirectedEdge {h :: Node, t :: Node} 
      | UndirectedEdge {a :: Node, b :: Node} 
instance Show Node where 
    show n = ['(', label n, ')'] 
instance Show Edge where 
    show (DirectedEdge h t) = show h ++ "->" ++ show t 
    show (UndirectedEdge a b) = show a ++ "-" ++ show b 

所以我區分了有向和無向邊。圖必須只有兩種類型的邊。我也有以下幾點：

nodes :: [Node] 
nodes = zipWith Node ['a'..] [0..] 

emptyGraph :: [Node] -> Graph edgeType 
emptyGraph ns = (ns, []) 

到目前爲止好，但我寫一個函數connect，與節點連接到現有的圖形。理想情況下，我只希望它適用於無向圖，但這似乎不是一種選擇。相反，我有這樣的事情：

connect :: Graph edgeType -> Node -> Graph edgeType 
connect (ns, es) n = (n:ns, e:es) 
    where e = UndirectedEdge n (head ns) 

但是，這提供了以下錯誤：

Couldn't match type `edgeType' with `Edge' 
    `edgeType' is a rigid type variable bound by 
      the type signature for 
       connect :: Graph edgeType -> Node -> Graph edgeType 

什麼是完成我想實現的最佳途徑？

Answer 1

你可能想有兩個單獨的邊緣，而不是類型的Edge

newtype DirectedEdge = DirectedEdge { h :: Node, t :: Node} 
newtype UndirectedEdge = UndirectedEdge { a :: Node, b :: Node} 

而且有可能需要某種類型類的，讓你回來(Node, Node)給出的任意邊緣：

class HasNodeEndpoints a where 
    endpoints :: a -> (Node, Node) 

-- obvious instances for DirectedEdge and UndirectedEdge 

然後，當你想談論任意圖形，你會寫Graph a，可能在HasNodeEndpoints a => Graph a工作的功能。關注圖類的算法分別適用於有向圖和無向圖的Graph DirectedEdge和Graph UndirectedEdge。

另一個自然延伸將被標記爲有向和無向邊緣。

class HasLabeled a where 
    type Label a -- associated type synonym 
    label :: a -> Label a 
    updateLabel :: a -> (Label a -> Label a) -> a 

-- now define data types and instances for labeled directed and undirected edges 

Answer 2

由於您選擇了特定的邊緣類型，即Edge，因此當您使用UndirectedEdge時，結果是圖形在邊緣類型中不再具有多態性。它必須有類型：

connect :: Graph Edge -> Node -> Graph Edge 
connect (ns, es) n = (n:ns, e:es) 
    where e = UndirectedEdge n (head ns) 

由於有野應其他類型的邊就可以了，因爲明確的使用UndirectedEdge。

---

順便說一句，我會使用節點上嚴格標註，就像良好的衛生事項：

data Node = Node { label :: !Char 
       , index :: !Int 
       } deriving (Ord, Eq)