实现类型类函数时无法匹配类型错误

Question

我正在尝试构建自己的简单图库，以便用于代码的出现。我有一个类型类Graph和一个使用Data.Map的具体实现MapGraph

class Graph g where
nodeSet :: (Ord n) => g -> S.Set n

data MapGraph e n = MapGraph {mGraph :: M.Map n [(e,n)]} deriving Show
instance (Ord e,Ord n) => Graph (MapGraph e n) where
nodeSet mapGraph = S.fromList $ M.keys $ mGraph mapGraph

如果nodeSet函数是实例声明之外的一个独立函数，那么它可以正常工作

testNodeSet mapGraph = S.fromList $ M.keys $ mGraph mapGraph
*Main> testNodeSet $ mapGraphFromEdgeList $ parseEdgeList connectionList
fromList ["B","C","D","E","F","G","H","I","J","K","L","S"]

但我在实例中收到了一个编译错误

Main.hs:59:22: error:
• Couldn't match type ‘n1’ with ‘n’
‘n1’ is a rigid type variable bound by
the type signature for:
nodeSet :: forall n1. Ord n1 => MapGraph e n -> S.Set n1
at Main.hs:59:3-9
‘n’ is a rigid type variable bound by
the instance declaration
at Main.hs:58:10-46
Expected type: S.Set n1
Actual type: S.Set n
• In the expression: S.fromList $ M.keys $ mGraph mapGraph
In an equation for ‘nodeSet’:
nodeSet mapGraph = S.fromList $ M.keys $ mGraph mapGraph
In the instance declaration for ‘Graph (MapGraph e n)’
• Relevant bindings include
mapGraph :: MapGraph e n (bound at Main.hs:59:11)
nodeSet :: MapGraph e n -> S.Set n1 (bound at Main.hs:59:3)
|
59 |   nodeSet mapGraph = S.fromList $ M.keys $ mGraph mapGraph
|                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

我不知道错误消息试图告诉我什么，只是我的类型签名有问题。tetsNodeSet的类型在我看来是正确的

testNodeSet :: Ord a => MapGraph e a -> S.Set a

我需要做些什么来解决我的问题？我确实想知道是否需要将(Ord e,Ord n) =>添加到数据类型MapGraph的声明中，但我无法在不出现编译错误的情况下将其添加到声明中

Answer 1

该类正在做出一个非常坚定的承诺，这在以后很难兑现：

class Graph g where
nodeSet :: (Ord n) => g -> S.Set n

这是有希望的，从任何Graph类型g，我们可以为任何有序类型n构建一组n。

也就是说，如果我们有instance Graph G where ...，那么从G我们必须能够构造S.Set Bool类型的nodeSet，S.Set Int、S.Set [Bool]等的S.Set String类型的另一个

很可能，这不是你想要的。你不想承诺"从图中可以得到任意类型的集合"；，但是类似于"；从图中可以得到一组固定类型的节点，这取决于图的类型"；。

这种依赖关系可以在Haskell中以多种方式表达，例如使用类型族

class Graph g where
type Node g
nodeSet :: g -> S.Set (Node g)   -- no need for Ord right now

这里我们声明了一个类型族Node g，它依赖于g。然后我们可以写

instance (Ord e,Ord n) => Graph (MapGraph e n) where
type Node (MapGraph e n) = n
nodeSet mapGraph = S.fromList $ M.keys $ mGraph mapGraph

以定义特定于手头实例的节点类型。

您需要启用一堆Haskell扩展来实现这一点，但希望这个想法是明确的。

---

以下是如何读取编译器的错误：

• Couldn't match type ‘n1’ with ‘n’

类型n1本应等于n，但事实并非如此。以下是这两种类型的来源：

‘n1’ is a rigid type variable bound by
the type signature for:
nodeSet :: forall n1. Ord n1 => MapGraph e n -> S.Set n1

n1是类中提到的类型(代码中称为n的类型(

‘n’ is a rigid type variable bound by
the instance declaration

n是实例中提到的类型(与n1无关(。

Expected type: S.Set n1
Actual type: S.Set n

该类承诺使用S.Set n1，但您的代码返回了S.Set n。要使这两种类型相等，我们需要n1和n相等，但不能保证它们是相等的。