Tạo một loại biểu đồ tham số trong Scala

Question

Tôi muốn tạo một hệ thống phân cấp kiểu chung để biểu diễn các đồ thị. Đặc biệt, tôi muốn có các lớp Graph và Node, và tôi muốn cho mọi kiểu đồ thị, có kiểu Node tương ứng và nếu tôi tạo một hàm chung để thao tác đồ thị, tôi muốn hàm này sử dụng nút thực tế kiểu. Một ví dụ mà tôi đã cố gắng

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 ... 

nhưng điều này không làm việc, bởi vì khi tôi đã làm

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

chức năng dfs sẽ không chấp nhận một chức năng của loại ConcreteGraph#Node=>Unit như nodeAction, nhưng chỉ AnyRef=>Unit hoặc GNode[ConcreteGraph]=>Unit.

Để được rõ ràng hơn, Nếu tôi đã làm nó trong C++, tôi muốn làm một cái gì đó giống như

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

Một ví dụ rất tốt của một cấu trúc đồ thị mở rộng là http://www.scala-lang.org/node/124

Tôi có ngươi cách để viết của bạn. Lưu ý rằng trong mọi trường hợp có một số thay đổi kiểu cần thiết - tức là tham số kiểu của GNode cần phải là biến thể, và ConcreteGraph cần phải được viết với cả một lớp nút riêng biệt và một kiểu ràng buộc cho nút.

Sau khi thực hiện, cách đầu tiên để viết dfs là làm cho nó trở thành một phương thức (nó có thể là cuối cùng nếu bạn muốn tránh chi phí công văn ảo).

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")} 

Thứ hai, với dfs không phải là phương pháp, dường như chỉ yêu cầu thêm một chút loại gợi ý để sử dụng nó.

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

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

Cách thứ ba là với dfs được cuộn. Do cách suy luận kiểu của Scala hoạt động, điều đó thực sự dẫn đến một giao diện rõ ràng hơn

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

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

Answer 2

Tôi không hiểu tại sao tất cả các thông số này là cần thiết. Các lớp bên trong trong Scala (không giống Java) có các kiểu phụ thuộc vào cá thể cụ thể của đối tượng bên ngoài. Cụ thể:

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 

Được cấp, bạn không thể xác định dfs bên ngoài biểu đồ nếu bạn muốn phụ thuộc vào loại phụ thuộc.