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)