Haskell 中的拟阵类型 class（错误）

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 应该是边类型？

copy/paste的代码：

{-# 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 不知道您想要 weightedG 的哪个 Matroid 实例。

它知道您想要 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。通过此更改，我得到了要编译的代码。

Haskell 中的拟阵类型 class（错误）

Matroid type class (error) in Haskell

haskell

greedy