Haskell中的Matroid类型类(错误)

Question

有限拟阵M是一对(E，I)，其中E是有限集(称为地集)，I是E的子集(称为独立集)。

加权拟阵是一个带有权函数w: e -> Int (正整数)的拟阵W。

我们可以定义(加权)拟阵类型如下：

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}

class Matroid matroid a where
  weight :: matroid -> a -> Int 
  groundSet :: matroid -> [a]
  indepSet :: [a] -> Bool

然后，我们可以为拟阵定义各种算法。例如，选择一个具有最小权重的基集F。当应用于图时，这是Kruskal的求最小权生成树的算法。

(加权)拟阵的一个例子是(加权)图G= (E，w)，其中E是边的集合，w是权函数。为了从图中定义拟阵，我们把地面集看作是边E的集合，E的子集F是独立的当且仅当它是无圈的。

instance Matroid WGraph Edge where
  weight = wT 
  groundSet = gSet
  indepSet = iSet

type Vertex = Int
type Edge = (Vertex, Vertex)
type Graph = [Edge]
type WtFun = Edge -> Int
type WGraph = (Graph, WtFun)

gSet :: WGraph -> [Edge]
gSet (es,wt) = es 

wT :: WGraph -> (WtFun)
wT (es,wt) = wt
-- stub
iSet :: [Edge] -> Bool
iSet edges = True

但是，给定一个加权图，下面的代码有一个类型错误

weightedG = (es, wt)::WGraph
es = [(4,5),(6,7),(5,7)]::[Edge]
wt :: (Edge -> Int)
wt (4,5) = 15
wt (6,7) = 11
wt (5,7) = 9
gs = groundSet weightedG

No instance for (Matroid WGraph a0)
  arising from a use of `groundSet'
The type variable `a0' is ambiguous

我们如何指定a0应该是边缘类型？

复制/粘贴代码：

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}

class Matroid matroid a where
  weight :: matroid -> a -> Int 
  groundSet :: matroid -> [a]
  indepSet :: [a] -> Bool

instance Matroid WGraph Edge where
  weight = wT 
  groundSet = gSet
  indepSet = iSet

type Vertex = Int
type Edge = (Vertex, Vertex)
type Graph = [Edge]
type WtFun = Edge -> Int
type WGraph = (Graph, WtFun)

gSet :: WGraph -> [Edge]
gSet (es,wt) = es 

wT :: WGraph -> (WtFun)
wT (es,wt) = wt

-- fix for real implementation
iSet :: [Edge] -> Bool
iSet edges = True

weightedG = (es, wt)::WGraph
es = [(4,5),(6,7),(5,7)]::[Edge]
wt :: (Edge -> Int)
wt (4,5) = 15
wt (6,7) = 11
wt (5,7) = 9
gs = groundSet weightedG

Answer 1

错误消息是指示GHC不知道您想要哪个Matroid实例用于weightedG。

它知道某些类型的Matroid WGraph a需要一个a，并且已经定义了一个实例Matroid Graph Edge，但是由于类型类是打开的，所以GHC无法得出结论，a必须是Edge。稍后或在另一个模块中，您(或其他人)可以定义一个Matroid WGraph String实例-例如。

其中一种方法是在拟阵类型和元素类型之间引入一个函数依赖关系，如下所示：

{-# LANGUAGE FunctionalDependencies #-}

class Matroid matroid a | matroid -> a where
   ...

这告诉GHC，matroid类型决定边缘类型a。通过这个更改，我可以编译您的代码。