无法在haskell中匹配具有特定类型的类类型

Question

我的代码中有以下情况(简化但语义相同)

class Graph a where
    edges :: EdgeSet c => a -> c

我有许多子类型可以实现图形界面.其中一个是树

data Tree = Tree

instance Graph Tree where
    edges tree = DirectedEdgeSet

对edge方法的调用应返回a DirectedEdgeSet.这应该没问题,因为DirectedEdgeSet实现了EdgeSet类:

type Edge = (Int, Int)
data DirectedEdgeSet = DirectedEdgeSet (Set Edge) Int

class EdgeSet c where
    content :: c -> Set Edge
    size :: c -> Int

instance EdgeSet DirectedEdgeSet where
    content (DirectedEdgeSet es _) = es
    size (DirectedEdgeSet _ x) = x 

此示例无法编译:

   • Couldn't match expected type ‘c’
                  with actual type ‘DirectedEdgeSet’
      ‘c’ is a rigid type variable bound by
        the type signature for:
          edges :: forall c. EdgeSet c => Tree -> c
        at Tree.hs:10:5
    • In the expression: DirectedEdgeSet
      In an equation for ‘edges’: edges tree = DirectedEdgeSet
      In the instance declaration for ‘Graph Tree’
    • Relevant bindings include
        edges :: Tree -> c (bound at Tree.hs:10:5)

有人能告诉我我做错了什么吗？

Answer 1

你误解了类方法的类型; edges :: EdgeSet c => a -> c是一个函数,它接受任何 a(约束a为一个实例Graph)并返回任何 c(约束c为一个实例EdgeSet c).你可能想要说它返回一些 c服从上述约束.

Haskell 98解决方案

你可以只要求边为所有图形返回一个实际的边Set(如一个边Data.Set):

class Graph a where
  edges :: a -> Data.Set Edge

ExistentialQuantification 解

否则,您可以使用ExistentialQuantification扩展名并修改类方法:

{-# LANGUAGE ExistentialQuantification #-}

data SomeEdgeSet = forall c. EdgeSet c => SomeEdgeSet c

class Graph a where
  edges :: a -> SomeEdgeSet 

instance Graph Tree where
  edges tree = SomeEdgeSet DirectedEdgeSet

正如你所知道的那样,你所使用的每一个实例Graph都会SomeEdgeSet在edges使用时返回,但是SomeEdgeSet包含任何东西,只要该东西是一个实例EdgeSet.

TypeFamilies 解

这是我推荐的解决方案.一般来说,对于任何一种Graph,你只会有一种类型的Edges返回.然后,有一个很酷的功能TypeFamilies,您可以在其中声明类中的类型:

{-# LANGUAGE TypeFamilies, UndecideableInstances #-}

class (EdgeSet (Edges a)) => Graph a where
  type Edges a
  edges :: a -> Edges a

然后,假设您的边缘表示Graph Tree为DirectedEdgeSet,您的实例将如下所示:

class Graph Tree where
  type Edges Tree = DirectedEdgeSet -- `DirectedEdgeSet` is the type here
  edges tree = DirectedEdgeSet      -- `DirectedEdgeSet` is the constructor here

Answer 2

在edges,类型变量c是普遍量化的.这意味着edges必须适用于所有类型的实例EdgeSet.您的实现修复了具体类型,因此不适用于所有 EdgeSet实例.

要解决此问题,您可以通过类型族指定实例使用的边集的具体类型:

{-# LANGUAGE TypeFamilies #-}

data Tree = Tree
data DirectedEdgeSet = DirectedEdgeSet

class Graph a where
  type GraphEdgeSet a :: *
  edges :: a -> GraphEdgeSet a

instance Graph Tree where
  type GraphEdgeSet Tree = DirectedEdgeSet
  edges tree = DirectedEdgeSet