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

Question

我正在尝试构建我自己的简单图形库，我可以使用它来编写代码。我有一个类型 class 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 做出了非常坚定的承诺，以后很难遵守：

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 String，依此类推S.Set Int，S.Set [Bool]，等等

很可能，这不是您想要的。您不想承诺“从图形中您可以获得任何类型的集合”，而是像“从图形中您可以获得一组固定类型的节点，这取决于图形类型”。

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

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

这里我们声明了一个依赖于g的类型族Node 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 是 class 中提到的类型（代码中称为 n 的类型）

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

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

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

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

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

Couldn't match type error when implementing type class function

haskell

graph

instance

typeclass

type-signature