关于使用函数依赖的帮助

Question

我有一个关于函数依赖的问题。我的理解是，例如，如果我编写class Graph g a b | g -> a, g -> b，那么任何特定的g只能与一种类型的a和b相关联。实际上，试图用相同g和不同的a和b声明两个实例是行不通的。

但是，在以下情况下，编译器(ghc)似乎无法使用依赖项，

class (Eq a, Eq b) => Graph g a b | g -> a, g -> b where
    edges :: g -> [b]
    src :: g -> b -> a
    dst :: g -> b -> a

    vertices :: g -> [a]
    vertices g = List.nub $ map (src g) (edges g) ++ map (dst g) (edges g)

class Graph g a b => Subgraph g a b | g -> a, g -> b where
    extVertices :: g -> [b]

data Subgraph1 g where
    Subgraph1 :: Graph g a b => g -> [b] -> Subgraph1 g

instance Graph g a b => Graph (Subgraph1 g) a b where
    vertices (Subgraph1 g _) = vertices g
    edges (Subgraph1 g _) = edges g
    src (Subgraph1 g _) = src g
    dst (Subgraph1 g _) = dst g

如果我通过将参数a和b添加到类型签名来修改Subgraph1，那么一切都会正常工作。

data Subgraph1 g a b where
    Subgraph1 :: Graph g a b => g -> [b] -> Subgraph1 g a b

Answer 1

不要使用fundeps，它们太痛苦了。使用关联类型。

class (Eq (Vertex g), Eq (Edge g)) => Graph g where
  type Edge   g :: *
  type Vertex g :: *

  edges :: g -> [Edge g]
  src   :: g -> Edge g -> Vertex g
  dst   :: g -> Edge g -> Vertex g

  vertices :: g -> [Vertex g]
  vertices g = nub $ map (src g) (edges g) ++ map (dst g) (edges g)

class Graph g => Subgraph g where
  extVertices :: g -> [Edge g]

data Subgraph1 g where
    Subgraph1 :: Graph g => g -> [Edge g] -> Subgraph1 g

instance Graph g => Graph (Subgraph1 g) where
    type Edge (Subgraph1 g) = Edge g
    type Vertex (Subgraph1 g) = Vertex g
    vertices (Subgraph1 g _) = vertices g
    edges (Subgraph1 g _) = edges g
    src (Subgraph1 g _) = src g
    dst (Subgraph1 g _) = dst g

这看起来更具可读性。Edge g是g的边的类型，等等。

请注意，我机械地翻译了您的代码，而没有理解Subgraph1做了什么。为什么这里需要GADT，数据构造函数的第二个参数是什么意思？它不会在任何地方使用。