在斯卡拉

Question

創建一個參數化圖形類型，我想創建一個通用的類型層次的代表圖。特別是，我想喜歡有班圖和節點，我想，對於每一個圖表類型，有相應的節點類型，如果我創建操作圖在通用的功能，我想這個功能使用實際的節點類型。我試過

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] { ... } 
} 

DFS功能不會接受ConcreteGraph#Node=>Unit類型的功能nodeAction一個例子，但只有AnyRef=>Unit或GNode[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) { ... } 

Answer 1

一個非常好的可擴展圖形結構的例子是在 http://www.scala-lang.org/node/124

我有你的方式寫你的。請注意，在所有情況下，都需要進行一些類型更改 - 即GNode的類型參數需要協變，並且需要使用不同的節點類和爲節點綁定的類型編寫ConcreteGraph。

一旦這樣做，寫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")} 

第二，如果dfs不是方法，似乎只需要一點額外的類型提示即可使用它。

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

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

第三種方法是用咖喱dfs。由於斯卡拉的類型推斷的方式，實際上導致更清潔的接口

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

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

Answer 2

我不明白爲什麼所有這些參數是必要的。 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。