5

グラフを表現するためのジェネリック型階層を作成したいと思います。特に、グラフとノードのクラスが必要です。すべてのグラフタイプに対応するノードタイプがあり、グラフを操作するためのジェネリック関数を作成する場合は、この関数で実際のノードを使用する必要があります。タイプ。私が試した例

trait GNode[Graph]
{
 ... functions to get edges from this vertex, etc. ...
}

trait Graph
{
  type Node <: GNode[Graph]
}

def dfs[G <: Graph](g : G, nodeAction : G#Node => Unit) = ... code ...

しかし、これはうまくいきませんでした。

class ConcreteGraph extends Graph
{
  class Node extends GNode[ConcreteGraph] { ... }
}

ConcreteGraph#Node=>Unitdfs関数は、タイプとしての関数を受け入れませんが、またはnodeActionのみを受け入れます。AnyRef=>UnitGNode[ConcreteGraph]=>Unit

明確にするために、私がC ++でそれをした場合、私は次のようなことをします

template <class T> struct graph_traits;
template <> struct graph_traits<concrete_graph> 
{ typedef concrete_graph::node node_type; }

template <class G>
void dfs(const G& g, boost::function<void(
           const graph_traits<G>::node_type&)> action) { ... }
4

2 に答える 2

7

拡張可能なグラフ構造の非常に良い例は、 http://www.scala-lang.org/node/124にあります。

私はあなたのものを書く3つの方法を持っています. すべての場合において、いくつかの型の変更が必要であることに注意してください。つまり、GNode の型パラメーターは共変である必要があり、ConcreteGraph は個別のノード クラスと Node にバインドされた型の両方で記述される必要があります。

完了したら、dfs を記述する最初の方法は、それをメソッドにすることです (仮想ディスパッチのオーバーヘッドを避けたい場合は、最終的なものにすることができます)。

trait GNode[+Graph] {
//... functions to get edges from this vertex, etc. ...
}

trait Graph {
  type Node <: GNode[Graph]

  def dfs(nodeAction : Node => Unit) = print("dfsing!")
}

class ConcreteGraph extends Graph {
  class CGNode extends GNode[ConcreteGraph]
  type Node <: CGNode
}

new ConcreteGraph dfs {node => println("foo")}

2 つ目は、メソッドではなく dfs を使用するため、それを使用するには、少しだけ追加の型ヒントが必要なようです。

def dfs[G <: Graph](graph : G, nodeAction : G#Node => Unit) = print("dfsing!")

dfs[ConcreteGraph](new ConcreteGraph, {node => println("foo")})

3 番目の方法は、カリー化された dfs を使用することです。Scala の型推論の仕組みにより、実際にはよりクリーンなインターフェイスが得られます。

def dfs[G <: Graph](graph : G)(nodeAction : G#Node => Unit) = print("dfsing!")

dfs(new ConcreteGraph){node => println("foo")}
于 2009-02-11T15:35:29.193 に答える
5

これらすべてのパラメーターが必要な理由がわかりません。Scala の内部クラス (Java とは異なり) には、外部オブジェクトの特定のインスタンスに依存する型があります。特に：

trait Graph {
  trait Node
  def dfs(n: Node) = println("DFSing!")
}

val graphA = new Graph {}
val nodeA = new graphA.Node {}
val graphB = new Graph {}
val nodeB = new graphB.Node {}
graphA.dfs(nodaA)  // prints "DFSing!"
graphB.dfs(nodeB)  // prints "DFSing!"
graphA.dfs(nodeB)  // type mismatch; found: graphB.Node required: graphA.Node
graphB.dfs(nodeA)  // type mismatch; found: graphA.node required: graphB.Node

確かに、依存型に依存したい場合は、グラフの外で dfs を定義することはできません。

于 2009-02-11T19:38:27.207 に答える