1

私は単純なグラフ構造を作ろうとしていて、次のように書きました。しかし、GHG はエラーを発生させ、私はそこにスタックしました。独自の型クラスを作成するのはこれが初めてなので、何かひどく間違っている可能性があります。誰かが何が間違っているのか説明できますか?

同様の質問を見つけましたが、私のケースには当てはまらないと思います.: 型クラスのインスタンスで型変数をバインドする際にエラーが発生しました

class Link l where
  node :: (Node n) => l -> n

class Node n where
  links :: (Link l) => n -> [l]

data (Node n) => SimpleLink n =
  SimpleLink
  { simpleLinkNode :: n
  } deriving (Show, Read, Eq)

instance (Node n) => Link (SimpleLink n) where
  node = simpleLinkNode

data (Link l) => SimpleNode l =
  SimpleNode
  { simpleNodeLinks :: [l]
  } deriving (Show, Read, Eq)

instance (Link l) => Node (SimpleNode l) where
  links = simpleNodeLinks

これは私が得たエラーメッセージです:

***.hs:13:10:Could not deduce (n ~ n1)
from the context (Node n)
  bound by the instance declaration
  at ***.hs:12:10-40
or from (Node n1)
  bound by the type signature for
             node :: Node n1 => SimpleLink n -> n1
  at ***.hs:13:3-23
  `n' is a rigid type variable bound by
      the instance declaration
      at ***.hs:12:16
  `n1' is a rigid type variable bound by
       the type signature for node :: Node n1 => SimpleLink n -> n1
       at ***.hs:13:3
Expected type: SimpleLink n -> n1
  Actual type: SimpleLink n -> n
In the expression: simpleLinkNode
In an equation for `node': node = simpleLinkNode

***.hs:21:11:Could not deduce (l ~ l1)
from the context (Link l)
  bound by the instance declaration
  at ***.hs:20:10-40
or from (Link l1)
  bound by the type signature for
             links :: Link l1 => SimpleNode l -> [l1]
  at ***.hs:21:3-25
  `l' is a rigid type variable bound by
      the instance declaration
      at ***.hs:20:16
  `l1' is a rigid type variable bound by
       the type signature for links :: Link l1 => SimpleNode l -> [l1]
       at ***.hs:21:3
Expected type: SimpleNode l -> [l1]
  Actual type: SimpleNode l -> [l]
In the expression: simpleNodeLinks
In an equation for `links': links = simpleNodeLinks

編集 1

ダニエルの提案をいくつか試しました。しかし、私はそれらを機能させることができませんでした。

コンストラクタークラス

取得: 「`n' が十分な型引数に適用されていません」

class Link l n where
  node :: Node n l => l n -> n l
class Node n l where
  links :: Link l n => n l -> [l n]

マルチパラメータ型クラス (MPTC)

取得: 「クラス宣言内の循環 (スーパークラス経由)」

class (Node n) => Link l n where
  node :: l -> n
class (Link l) => Node n l where
  links :: n -> [l]

機能依存関係のある MPTC

取得: 「クラス宣言内の循環 (スーパークラス経由)」

class (Node n) => Link l n | l -> n where
  node :: l -> n
class (Link l) => Node n l | n -> l where
  links :: n -> [l]

目標 (編集 2)

実装したいのは、次のような有向非巡回グラフ構造 (より具体的にはFactor graph ) です。

PRML 図 8.51
(ソース: microsoft.com )

ノードには 2 種類 (白丸と赤四角) があり、異なる種類のノードにのみ接続されます。つまり、2 種類のリンクが存在します。

データ (配列) が接続されたノードとリンクの異なるバージョンが必要です。また、ノードとリンクが 1 種類しかない「バニラ」DAG も必要です。しかし、それらをトラバースするために、それを行うためのインターフェースを 1 つだけにしたいと考えています。

4

4 に答える 4

4

誰かが何が間違っているのか説明できますか?

エラー メッセージについて説明する前に最初の問題を説明します。ポリモーフィック データ型は適切ですが、最終的には具象型を使用する必要があります。

種類の SimpleNode と種類* -> *の SimpleLinks* -> *では、具象型はありません。

SimpleNode (SimpleLink (SimpleNode (SimpleLink (SimpleNode (...

Haskell では無限型を持つことはできませんが、 newtype と data はより近くなります。

type G0 = SimpleNode (SimpleLink G0)  -- illegal
newtype G1 = G1 (SimpleNode (SimpleLink G1))   -- legal
data G2 = G2 (SimpleNode (SimpleLink G2))   -- legal

型クラスを作成する前に、データ型を再考する必要があるかもしれません。

エラーメッセージの説明に移りましょう: あなたの型クラスLinkは関数を定義していますnode

class Link l where
  node :: (Node n) => l -> n

はnode魔法の OOP ファクトリで、 の型と値を指定すると、( で囲まれた)l任意の型をウィッシュの呼び出し元にすることができます。これはあなたのインスタンスとは関係ありません:nNode nnodenn

instance (Node n) => Link (SimpleLink n) where
  node = simpleLinkNode

繰り返しnますが、上記の例の は定義と同じnではありません。node :: (Node n) => l -> nコンパイラは関連するが新しい名前n1を作成し、エラーを返します。

  `n' is a rigid type variable bound by
      the instance declaration
      at ***.hs:12:16
  `n1' is a rigid type variable bound by
       the type signature for node :: Node n1 => SimpleLink n -> n1
       at ***.hs:13:3

インスタンス内のnは、関数への入力の型 (SimpleLink n) から取得されnodeます。のn1呼び出し元がnode、この魔法の工場で生産するよう要求しているタイプです。n と n1 が同じ場合、コンパイラは満足しますが、型クラスとインスタンスの定義はこれを制約しないため、コード スニペットは拒否されます。

SimpleLink のエラーについても同様の話が繰り返されます。これに対する特効薬はありません。目標を達成する方法を学ぶために、おそらく他の人のコードを読んだ後、これを再考して再設計する必要があると思います。

あなたの目標は何ですか？グラフのデータ構造は非常に多様であり、詳細が重要です。

于 2012-07-10T22:16:39.340 に答える
1

私はスタックオーバーフローのエチケットを破り、これを分離するために2番目の答えを追加しています。これは、ラベルのないエッジを持つ2部無向グラフの簡単なコード例であり、因子グラフのモデル化に役立つ可能性があります。

-- Bipartite graph representation, unlabeled edges

-- Data types to hold information about nodes, e.g. ID number
data VariableVertex = VV { vvID :: Int }  deriving (Show)
data FactorVertex = FV { fvID :: Int }  deriving (Show)

-- Node holds itself and a list of neighbors of the oppostite type
data Node selfType adjacentType =
  N { self :: selfType
    , adj :: [Node adjacentType selfType] }

-- A custom Show for Node to prevent infinite output
instance (Show a, Show b) => Show (Node a b) where
  show (N x ys) = "Node "++ show x ++ " near " ++ show (map self ys)

-- Type aliases for the two node types that will be used
type VariableNode = Node VariableVertex FactorVertex
type FactorNode = Node FactorVertex VariableVertex

data FactorGraph = FG [VariableNode] [FactorNode]  deriving (Show)

v1 = N (VV 1) [f1,f2]
v2 = N (VV 2) [f2]
v3 = N (VV 3) [f1,f3]
f1 = N (FV 1) [v1,v3]
f2 = N (FV 2) [v1,v2]
f3 = N (FV 3) [v3]

g = FG [v1,v2,v3] [f1,f2,f3]
于 2012-07-12T11:19:49.327 に答える
0

Chris Kuklewicz (http://stackoverflow.com/a/11450715/727827) からヒントを得て、最初に必要なコードを取得しました。

ただし、クリスの答え（*Vertexデータを保持するために使用する）はシンプルで優れていると思います。私が望んでいたことを明確にするために、これをここに残します。

class NodeClass n where
  adjacent :: n a b -> [n b a]

data Node selfType adjacentType =
  N
  { selfNode :: selfType
  , adjNode :: [Node adjacentType selfType] }

data NodeWithData selfType adjacentType =
  NWD
  { selfNodeWithData :: selfType
  , adjNodeWithData :: [NodeWithData adjacentType selfType]
  , getDataWithData :: [Double]
  }

instance NodeClass Node where
  adjacent = adjNode

instance NodeClass NodeWithData where
  adjacent = adjNodeWithData

data VariableVertex = VV { vvID :: Int }  deriving (Show)
data FactorVertex = FV { fvID :: Int }  deriving (Show)

type VariableNode = Node VariableVertex FactorVertex
type FactorNode = Node FactorVertex VariableVertex

type VariableNodeWithData = NodeWithData VariableVertex FactorVertex
type FactorNodeWithData = NodeWithData FactorVertex VariableVertex
于 2012-07-12T16:40:14.223 に答える