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