1

機能依存性について質問があります。私の理解では、たとえば、私が書く場合class Graph g a b | g -> a, g -> b、特定のものは1つのタイプのとgにのみ関連付けることができます。実際、同じで異なる2つのインスタンスを宣言しようとすると、機能しません。abgab

ただし、次の場合、コンパイラ（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

パラメータと型アノテーションSubgraph1を追加して修正すると、すべてがうまくいきます。ab

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

1 に答える 1

4

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が必要なのはなぜですか。また、データコンストラクターの2番目の引数は何を意味しますか。どこにも使用されていません。

于 2011-07-23T09:29:37.293 に答える